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

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)?

CodePudding user response：

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.

CodePudding user response：

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)