By itself, this loop will iterate through ceil(log(n))
times. That's log(n)
with log base of 2. This is because after ceiling(log(n))
multiplications, i
will have reached or passed n
, for any n
. A quick example:
For n=100:
Iteration: i:
1 1
2 2
3 4
4 8
5 16
6 32
7 64
8 128
So i
will be checked on the 8th iteration and you don't go into the loop, as it's not <= 100
. It will be nlog2(n)
as you suggest if there's another inner loop that fully loops through n
times. Then the two times for the two loops get multiplied to get the total time.