Search code examples
for-loopbig-ocomputer-science

How do I calculate this logarithmic complexity using summations?

My Question

What is the Big-O complexity for this code snippet? Consider n as a power of 4.

for(int i = 1; i <= n; i = i*4)                      
    for(int k = 1; k <= i; k++)                 
       // constant statement

What I know so far

I tried making this code into a summation to find the complexity. This is what I got: enter image description here

I got (base 4) log(n) by computing the series 4, 4^2, 4^3 ... 4^r = n. r = (base 4) log(n).

I'm now stuck at this summation:

enter image description here

Please let me know If I'm doing something wrong or there is another way to do this.

Solution

  • You’re on the right track here, but your innermost summation is wrong. You are right that the outer loop will iterate log_4 n times, but you’ve set up the outer sum so that i counts up as 1, 2, 3, ..., log_4 n, rather than 4^0, 4^1, 4^2, ... 4^log_4 n. As a result, that inner summation’s upper bound is incorrect. The bound should be 4^i, not i.

    If you set things up this way, you’ll find that the overall sum is

    4^0 + 4^1 + 4^2 + ... + 4^log_4 n

    = (4^(log_4 n + 1) - 1) / (4 - 1) (using the formula for the sum of a geometric series

    = (4(4^log_4 n) - 1) / 3

    = (4n - 1) / 3

    = Θ(n).