1
$\begingroup$

This is the code:

j=2
while j<(n*n)
     j=j*j

At first my approach was to treat this like this loop

i=1
while (i<n)
    i=i*2

Which generates on $i$ various powers of $2$ ($i=2^0, 2^1, 2^2....2^k$).

At a certain $k$ iteration, $i$ is equal to or exceeds $n$. So $2^k=n$ is the time when the while stops.

We find $k=log_2(n)$ which is the number of times the entire while loop has been executed, so $T(n)=\theta(log_2n)$.


So my idea for the first algorithm was this: j=j*j generates on $j$ different powers of himself, so you can describe it as $j^2$. The problem is that I can't shove in a $k$ iterations in the counting.

The solution for this is actually $log(log(n))$.

Why is this? Can I improve my logic?

$\endgroup$
2
$\begingroup$

Iterating i=2*i generates the powers of two, as you mentioned.

$$ 2=2^1 \quad 2*2^1=2^2 \quad 2*2^2 = 2^3 \quad 2*3^2 = 2^4 \quad \ldots $$

Iterating j=j*j instead does something more aggressive:

$$ 2 = 2^1 \quad 2^1*2^1=2^2 \quad 2^2*2^2=2^4 \quad 2^4*2^4=2^8 \quad\ldots $$

Note how the exponents grow. In the i sequence they are $1,2,3,4,\ldots$. But in the j sequence they are $1,2,4,8,\ldots$. That is, the exponents themselves grow exponentially!

So, the $k$-th element in the first sequence is $2^k$ while in the second it is $2^{2^k}$. That's why the first loop has complexity $O(\log_2 n)$ and the second one $O(\log_2 (log_2 n))$.

$\endgroup$
2
$\begingroup$

You're on the right track. For the simpler code, you correctly wrote down the sequence of values that are produced: $2^0,2^1,2^2,\dots$. In particular, the $t$th output is $2^t$. Then you were able to find where the loop stops by setting $2^t=n$ and solving for $t$. That's a great approach.

Try doing the same thing for your actual example. Hint: the first two outputs are $j$ and $j^2$. What's next? Can you generalize What is the $t$th output? Can you write an equation that represents where the loop stops and solve for $t$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.