Time complexity of the java code

Question

I am taking up algorithm course on coursera,and I am stuck on this particular problem. I am supposed to find the time complexity of this code.

int sum = 0

 for (int i = 1; i <= N*N; i = i*2)

  {
     for (int j = 0; j < i; j++)
           sum++; 
  }

I checked it in eclipse itself, for any value of N the number of times sum statement is executed is less than N

final value of sum:
for N=8 sum=3 
for N=16 sum=7 
for N=100000 sum=511

so the time complexity should be less than N but the answer that is given is N raised to the power 2, How is it possible?

What I have done so far:

the first loop will run log(N^ 2) times, and consequently second loop will be execute 1,2,3.. 2 logN

Why would you even have that inner loop? Why not just sum += i? — user207421
– user207421, Commented Aug 13, 2012 at 1:07

Peter Lawrey · Accepted Answer · 2012-08-12 20:18:35Z

3

The first inner loop will be 1 + 2 + 4 + 8 .. 2^M where 2^M is <= N * N.

The sum of powers of 2 up to N * N is approximately 2 * N * N or O(N ^ 2)

Note: When N=100000 , N*N will overflow so its result is misleading. If you consider overflow to be part of the problem, the sum is pretty random for large numbers so you could argue its O(1), i.e. if N=2^15, N^2 = 2^30 and the sum will be Integer.MAX_VALUE. No higher value of N will give a higher sum.

edited Aug 12, 2012 at 20:18

answered Aug 12, 2012 at 19:50

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

huseyin tugrul buyukisik Over a year ago

try in an optimizer and see that it is O(1)

Sahil Over a year ago

how is 1 + 2 + 4 + 8 .. 2^M (N^2 ) plz explain this

Peter Lawrey Over a year ago

The sum of powers of 2 up to 2^M is 2^(M+1) - 1. I knew the proof in high school but don't have much use for mathematical proofs these days. ;) You can see the pattern if you try it. 1, 3, 7, 15, 31, 63, 127, 255 etc.

Sahil Over a year ago

yes the value of M is log N^2 and 2 ^ (log N^ 2) is N^2 I hope it is correct

Peter Lawrey Over a year ago

Using log appeared to make sense until Saeed pointed out it was wrong. I realized that the sum of powers of 2 is just basically 2 * the maximum which is N^2 so the O(N^2). log doesn't come into it.

|

vidstige · Accepted Answer · 2012-08-12 20:33:31Z

3

There is a lot of confusion here, but the important thing is that Big-O notation is all about growth rate, or limiting behavior as mathematicians will say. That a function will execute in O(n*n) means that the time to execute will increase faster than, for example n, but slower than, for example 2^n.

When reasoning with big-O notation, remember that constants "do not count". There is a few querks in this particular question.

The N*N expression it-self would lead to a O(log n*n) complexity if the loop was a regular for-loop...
...however, the for-loop increment is i = i*2 causing the outer loop to be executed approximately log n and the function would be in O(log n) if the contents of the inner loop run in a time independent of n.
But again, the inner-loop run-time depends on n, but it doesn't do n*n runs, rather it does roughly log (n*n)/2 loops. Remembering that "constants don't count" and that we end up in O(n*n).

Hope this cleared things up.

edited Aug 12, 2012 at 20:33

answered Aug 12, 2012 at 19:52

vidstige

13.1k9 gold badges70 silver badges115 bronze badges

3 Comments

nhahtdh Over a year ago

Nope, the for-loop is i *= 2. Not i *= i.

Gir Over a year ago

the loop increment isnt i*=i its i*=2

nhahtdh Over a year ago

Your explanation is incorrect, though. If the inner loop is O(1) (independent of n), the outer loop will run in O(log(n)).

Roman Dzhabarov · Accepted Answer · 2012-08-12 20:13:34Z

2

So sum ++ will be executed 1 + 2 + 4 + 8 + ... + N*N, total log2(N*N) times. Sum of geometrical progression 1 * (1 - 2 ^ log2(N*N)/(1 - 2) = O(N*N).

answered Aug 12, 2012 at 20:13

Roman Dzhabarov

5214 silver badges10 bronze badges

Comments

SJuan76 · Accepted Answer · 2012-08-12 19:51:37Z

0

Your outer loop is log(N^2)->2*log(N)->log(N), your inner loop is N^2/2->N^2. So, the time complexity is N^2*log(N).

About the benchmark, values with N=8 or N=16 are ridiculous, the time in the loop is marginal in relation with setting JVM, cache fails, and so on. You must:

Begin with biggest N, and check how it evaluate.

Make multiple runs with each value of N.

Think that the time complexity is a measure of how the algorithm works when N becomes really big.

answered Aug 12, 2012 at 19:51

SJuan76

24.9k7 gold badges52 silver badges95 bronze badges

4 Comments

Sahil Over a year ago

How is inner loop N^2/2? I understand the value of outer loop?

SJuan76 Over a year ago

Ok, I was too fast there. I was thinking about arithmetic succession (1 iterations when i=2, 2 iteration when i = 3...) but didn't think that i goes takes values 1, 2, 4, 8, 16... It is a sum of values of a geometric serie, I have to check it again.

Sahil Over a year ago

Yes that is what think, the inner loop is not that simple

SJuan76 Over a year ago

1 + 2 = 3 (2^2 -1), 1 + 2 + 4 = 7 (2^3 - 1)... in general, the iterations will be 2^i - 1 for a given i

Collectives™ on Stack Overflow

Time complexity of the java code

4 Answers 4

6 Comments

3 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

3 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related