Is this algorithm O(log log n) complexity?

Question

In particular, I'm interested in finding the Theta complexity. I can see the algorithm is bounded by log(n) but I'm not sure how to proceed considering the problem size decreases exponentially.

i = n
j = 2
while (i >= 1)
    i = i/j
    j = 2j

Answer 1

The simplest way to answer your question is to look at the algorithm through the eyes of the logarithm (in my case the binary logarithm):

log i_0 = log n
log j_0 = 1
k = 0
while (log i_k >= 0) # as log increases monotonically
    log i_{k+1} = log i_k - log j_k
    log j_{k+1} = (log j_k) + 1
    k++

This way we see that log i decreases by log j = k + 1 during every step.
Now when will we exit the loop?
This happens for

The maximum number of steps is thus the smallest integer k such that
holds.
Asymptotically, this is equivalent to , so your algorithm is in