Analysis of Typical Loops
for( int j = 1; j
<= n; j = 2*j )
{
O(1)
}
Complexity:
O(log(n)) This bound is
tight.
j doubles each time.
The loop stops by iteration k,
where 2k
>= n, i.e. by
ceiling(log(n)) iterations.