-1
\$\begingroup\$

I have a two-dimensional array with M rows and N columns, with each element having a value between 0 and 255.

I have a second two-dimensional array with m rows and n columns, m < M, n < N.

The second array is like a box inside the first array, and loops from the top left to bottom right corner of the first array. With each loop, the mean of the elements of the second array is calculated. The purpose of the algorithm is to find the box from the first array that has the greatest mean (it stores the row and column indexes where the window array starts, within minI and minJ variables).

The following is an image which would help you understand better the idea of the algorithm: enter image description here

Here is the code:

for(int i = 0;i <= M - m;i++){
            for(int j = 0;j <= N - n;j++){
                suma = 0;
                for(int k = i;k < i + m;k++){
                    for(int p = j; p < j + n;p++){
                        suma += A[k][p];
                    }
                }

                if(suma > max){
                    max = suma;
                    maxI = i;
                    maxJ = j;
                }
            }
        }

I want to know the complexity of this algorithm, and the way you calculate it.

\$\endgroup\$

closed as off-topic by Graipher, Toby Speight, Mast, Stephen Rauch, yuri Sep 10 '18 at 15:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – Graipher, Toby Speight
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Toby Speight Sep 10 '18 at 10:22
  • 2
    \$\begingroup\$ I'm voting to close this question as off-topic because the help center specifically states you have to want a review of your code for it to be a valid question. This is not a request for review, it's a "explain to me how to calculate Big O" question. Asked and answered on plenty other of other places of the internet, don't do it here. \$\endgroup\$ – Mast Sep 10 '18 at 10:29
  • \$\begingroup\$ @Mast I understand. Can you please suggest which place would be suitable for asking about algorithm complexity ? Stack Overflow, maybe ? \$\endgroup\$ – Narcis Neacsu Sep 10 '18 at 10:54
0
\$\begingroup\$

To calculate the complexity of any algorithm, you have to check how many basic operations that algorithm performs. In your case, your basic operation is suma += A[k][p];. That operation will take up the majority of your runtime.

So, how many times is that line of code executed? To calculate that, we count the loops:

  1. for(int i = 0;i <= M - m;i++) executes \$M-m\$ times
  2. for(int j = 0;j <= N - n;j++) executes \$N-n\$ times for each iteration in (1)
  3. for(int k = i;k < i + m;k++) executes \$m\$ times for each iteration in (2)
  4. for(int p = j; p < j + n;p++) executes \$n\$ times for each iteration in (3)

To get the result, just multiply them together:

\[O((M-m)(N-n)mn) = O(MNmn + m^2n^2-Mmn^2 - Nm^2n)\]

From your sketch, it looks like \$m, n\$ are relatively small compared to \$M, N\$. If this is the case, or if \$m<N\$ and \$n<M\$,you can simplify the above formula:

\[\approx O(MNmn)\]

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.