CODEWITHSUNDEEP
loopstime-complexitybig-o
mark
mark

Reputation: 93

Why is it O(log(logn)) instead of O(logn)

p = 0
for( i=1; i<n; i=i*2 ) { 
    p++ // log n 
} 

for( j=1; j<p; j=j*2 ) { 
    some_statement // log P
}
//  O( log log n )

Why a variable coming from an independent loop affects another loop's time? And if we were to delete the second loop, time complexity would be just O(logn) which is more slower. Why the time complexity isn't just logn + logn = 2logn therefore O(logn)?

Upvotes: 2

Views: 138

Answers (2)

Ryan
Ryan

Reputation: 184

By creating the second loop

for( j=1; j<p; j=j*2 ) { 
    some_statement // log P
}

You have added additional time complexity based on the input parameter n. After executing loop 1, we will have p = log2 n, meaning your second loop becomes

for( j=1; j< log2 n; j=j*2 ) { 
    some_statement // log2 (log2 n)
}

So the total time complexity of loop1 and loop2 = loop1 + loop2 = log2n + log2(log2(n)) which is O(logn)

Upvotes: 2

Berthur
Berthur

Reputation: 4495

Because they are not independent: The first computes p = O(log n) and the second depends on it. The time complexity of the second loop would be O(log p) = O(log log n).

However, the first loop is still O(log n), which indeed makes the time complexity of the entire program O(log n + log log n) = O(log n), as you say.

Upvotes: 2

Related Questions