for(j=n; j>1; j/=2)
++p;
for(k=1; k<p; k*=2)
++q;
On the first code sample, p variable belong to 1st loop. So,even they are not nested loop,will 2nd return log(n),too? I mean totally, O(loglog(n))?
for(i=n; i>0; i--){
for(j=1; j<n; j*=2){
for(k=0; k<j; k++){
//statements-O(1)
}
}
}
And these one, they are nested but k variable belong to 2nd loop. So, should it similar to 1st one? Like O(n^2.log(n)) or O(n.log^2(n))?
Algorithm: First loop takes log(n) time. Second loop takes log(log(n)) time. So you have log(n) + log(log(n)). But first loop counts more. So it's O(log(n)).
Algorithm: At first look what runtime you have when you only analyse the two outer for loops (means n log(n)). But unfortunately there comes an inner third for loop which makes it more complex.
The third for loop counts from 0 to 2^m where m=log(n). So you have to sum 2^m from 0 to log(n)-1 which is n-1. So n-1 is the run time of the two inner for loops. Now you have to multiply it by the linear run time of the outer for loop. So it's (n-1)n which is n²-n. So you have O(n²) for the three loops.
