CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theorylogarithm
Francisco Pizarro
Francisco Pizarro

Reputation: 45

Is this algorithm O(log log n) complexity?

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

Upvotes: 3

Views: 1849

Answers (2)

Tobias Ribizel
Tobias Ribizel

Reputation: 5421

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
0 > log i_k = log n - (sum from m = 1 to k of m) = log n - k(k+1)/2
The maximum number of steps is thus the smallest integer k such that
k(k + 1) / 2 > log n holds.
Asymptotically, this is equivalent to k²/2 > log n, so your algorithm is in Theta(sqrt(log n))

Upvotes: 4

Damien Prot
Damien Prot

Reputation: 593

Let us denote i(k) and j(k) the value of i and j at iteration k (so assume that i(1)=n and j(1)=2 ). We can easily prove by induction that j(k)=2^k and that

enter image description here

Knowing the above formula on i(k), you can compute an upper bound on the value of k that is needed in order to have i(k) <= 1 and you will obtain that the complexity is enter image description here

Upvotes: 2

Related Questions