Time complexity analysis of code

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

I need to analyze its time complexity. I noticed it reaches n much faster than just log(n). I mean, it does less steps than O(log(n)) would do. I read the answer but have no idea how they got to it: It is O(log(log(n)). Now, how do you approach such a question?

Answer 1

think of it as a recursive function:

f(i) = f(i-1)^3

if you expand it:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

the function grows as the power of the power... so the time (iterations) to reach a certain number (that is, calculating the inverse of the function) is the logarithm of the logarithm.

As in your example f(0) = 2, we want to know when f(i) >= n being n the input parameter (and i the number of iterations):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

So to reach a value of n, it takes log_3(log_2(n)) iterations (round up while dealing with integers to surpass it).

if the function would be:

f(i) = 2*f(i-1) //e.g. x=2*x

then the pattern would be:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

And in this case, then the inverse of the function would be a single logarithm in base 2.

My math is not very rigorous, but I hope you'll get the idea.

Answer 2

Think about how x changes with the number of iterations through the loop. Each time, you cube it. So after i iterations, the value will be 2 cubed, cubed again... and so on, i times. Let's use x(i) to denote this expression. Let's say x(0)=2, x(1)=23, etc (I'm using ab to mean a raised to the bth power).

We're done when x(i)>=n. How long does it take? Let's solve for i.

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

We can ignore the constant factors, and we're left with the conclusion that we'll take log(log(n)) steps. That's the complexity of your algorithm.

Hopefully, breaking down all the steps like that helps.