1

I have an assignment I am not sure with; I have to calculate the time complexity of the following code:

int a[][] = new int[m][n];        //O(1)
int w = 0;                        //O(1)
for (int i = 0; i < m; i++)       //O(n)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(logn)
         w++;                     //O(1)

So from my O estimations I add them up:

O(1) + O(1) + O(n) * ( O(n) * ( O(logn) + O(1) / 2 ) )
O(1) + O(1) + O(n) * ( O(nlogn) + O(n) / 2 )
O(1) + O(1) + (O(n2logn) + O(n2) / 2)
=O(n2logn)

I'm not sure if my train of thought is correct, could somebody help?

xenteros
  • 15,586
  • 12
  • 56
  • 91
RVER12321312
  • 81
  • 8
  • That log is wrong. The complete complexity is just quadratic. (The if is just a constant operation assuming modulo is constant) – sascha Oct 05 '16 at 15:00
  • @sascha it's not quadratic. – xenteros Oct 05 '16 at 15:08
  • @sascha Oh I see... I had in my notes somewhere my lecturer mentioned that because there was a chance for the variables to be %2 and it is o(logn) for some reason. Thanks – RVER12321312 Oct 05 '16 at 15:09

3 Answers3

3
 for (int i = 0; i < m; i++)  //O(m)
  {   
    for (int j = 0; j <n; j++) //O(n)
    {
      // your code
    }
  }

So the i loop will go on m times, and for the j loop would run n times. So in total the code will go on m*n times which would be its time complexity: O(m.n)

xenteros
  • 15,586
  • 12
  • 56
  • 91
Viveka Agarwal
  • 56
  • 6
  • so the o(m) and o(n) variables should be treated independently as opposed to o(n^2) for running the for loop twice? – RVER12321312 Oct 05 '16 at 15:11
  • if the for loop is run twice(each time upto n times), then there will be two independent O(n) computations(considering it's a loop within a loop). O(n) for the outer loop and O(n) for the inner loop, resulting in O(n^2). – Viveka Agarwal Oct 05 '16 at 18:11
  • But if it's two separate for loops, each running upto n , then it will be O(n) +O(n) = O(2n) which is the same as O(n) – Viveka Agarwal Oct 05 '16 at 18:12
3
for (int i = 0; i < m; i++)       //O(m)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(1)
         w++;                     //O(1)

So the total complexity in terms of is:

O(m)*(O(n) + O(1) + O(1)) = O(m)*O(n) = O(m*n).

xenteros
  • 15,586
  • 12
  • 56
  • 91
  • You're adding apples to oranges. You cannot tell the `int a[][] = new int[m][n];` is `O(1)` while `for (int i = 0; i < m; i++)` is `O(m)`. It's really a super non-scientific and misleading way to do the Big-O complexity analysis. – zerkms Oct 06 '16 at 05:44
  • @zerkms I agree. It's `O(mn)`. Didn't think about the initialization. – xenteros Oct 06 '16 at 05:49
  • Not only that - my point is that you cannot simply add arbitrarily put `O()` approximations together. Simple reason: why do you assume `new int[m][n]` is fixed time? – zerkms Oct 06 '16 at 05:50
  • Now it's even worse :-) I would not sum them at all. But I'm not insisting on it :-) – zerkms Oct 06 '16 at 05:51
-1

The final complexity is O(n^2)

Your logic is close except...

int a[][] = new int[m][n];        //O(1)
int w = 0;                        //O(1)
for (int i = 0; i < m; i++)       //O(n)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(1)
         w++;                     //O(1)

Your if statement embedded in your second for loop is simply referencing an element in an array and doing a basic comparison. This is of time complexity O(1). Also, typically you would not consider initializing variables in a time complexity problem.

Preston Martin
  • 2,789
  • 3
  • 26
  • 42