CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theorynested-loopscode-analysis
Rares Andrei
Rares Andrei

Reputation: 81

Hard Big O complexity for 3 loops

I try to calculate Big O complexity for this code but I always fail....

I tried to nest SUM's or to get the number of steps for each case like:

then sum all the steps together, I need help.

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

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

      for(int k=1; k<=j*j; k++)

           //code line with complexity code O(1)

Upvotes: 1

Views: 569

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114230

Let's take a look at the number of times the inner loop runs: j2. But j steps along in powers of 2 up to i. i in turn steps in powers of 2 up to n. So let's "draw" a little graphic of the terms of the sum that would give us the total number of iterations:

  ---- 1
   ^   1 4
   |   1 4 16
log2(n)   ...
   |   1 4 16 ... n2/16
   v   1 4 16 ... n2/16 n2/4
  ---- 1 4 16 ... n2/16 n2/4 n2
       |<------log2(n)------>|

The graphic can be interpreted as follows: each value of i corresponds to a row. Each value of j is a column within that row. The number itself is the number of iterations k goes through. The values of j are the square roots of the numbers. The values of i are the square roots of the last element in each row. The sum of all the numbers is the total number of iterations.

Looking at the bottom row, the terms of the sum are (2z)2 = 22z for z = 1 ... log2(n). The number of times that the terms appear in the sum is modulated by the height of the column. The height for a given term is log2(n) + 1 - z (basically a count down from log2(n)).

So the final sum is

log2(n)
  Σ  22z(log2(n) + 1 - z)
 z = 1

Here is what Wolfram Alpha has to say about evaluating the sum: http://m.wolframalpha.com/input/?i=sum+%28%28log%5B2%2C+n%5D%29+%2B+1+-+z%29%282%5E%282z%29%29%2C+z%3D1+to+log%5B2%2C+n%5D:

C1n2 - C2log(n) - C3

Cutting out all the less significant terms and constants, the result is

O(n2)

Upvotes: 2

dfrib
dfrib

Reputation: 73176

For the outermost loop:

  sum_{i in {1, 2, 4, 8, 16, ...}} 1, i <= n (+)

  <=>

  sum_{i in {2^0, 2^1, 2^2, ... }} 1, i <= n

Let 2^I = i:

  2^I = i <=> e^{I log 2} = i <=> I log 2 = log i <=> I = (log i)/(log 2)

Thus, (+) is equivalent to

  sum_{I in {0, 1, ... }} 1, I <= floor((log n)/(log 2)) ~= log n                      (*)

Second outermost loop:

  sum_{j in {1, 2, 4, 8, 16, ...}} 1, j <= i (++)

As above, 2^I = i, and let 2^J = j. Similarly to above,
(++) is equivalent to:

  sum_{J in {0, 1, ... }} 1, J <= floor((log (2^I))/(log 2)) = floor(I/(log 2)) ~= I   (**)

To touch base, only the outermost and second outermost
have now been reduced to

  sum_{I in {0, 1, ... }}^{log n} sum_{J in {0, 1, ...}}^{I} ...

Which is (if there would be no innermost loop) O((log n)^2)

Innermost loop is a trivial one if we can express the largest bound in terms of `n`.

  sum_{k in {1, 2, 3, 4, ...}} 1, k <= j^2 (+)

As above, let 2^J = j and note that j^2 = 2^(2J)

  sum_{k in {1, 2, 3, 4, ...}} 1, k <= 2^(2J)

Thus, k is bounded by 2^(2 max(J)) = 2^(2 max(I)) = 2^(2 log(n) ) = 2n^2                (***)

Combining (*), (**) and (***), the asymptotic complexity of the three nested loops is:

  • O(n^2 log^2 n) (or, O((n log n)^2)).

Upvotes: 2

Related Questions