Chandra G. answered • 02/19/21

Phd In Computer Science, Lead Developer for DataBlitz, on Unix

The terminating condition of the while loop is

j <= n

Inside the while loop the terminating condition is reduced by the following statement

j = j* 2;

The other statement inside the while loop takes constant time.

sum ++ ;

So now, the question is HOW many times does the while loop iterate ?

Consider n = 2

The statement j = j*2 executes 2 times and the condition j <= n is executed 3 times

Consider n = 3

The statement j = j*2 executes 3 times and the condition j <= n is executed 4 times

Consider n = 4

The statement j = j*2 executes 3 times and the condition j <= n is executed 4 times

INTERESTING! now let's check n=5

The statement j = j*2 executes 3 times and the condition j <= n is executed 4 times

The same thing for n=6,7 - The statement j = j*2 executes 3 times and the condition j <= n is executed 4 times

But, when n=8,

The statement j = j*2 executes 4 times and the condition j <= n is executed 5 times

The pattern that emerges is that the statement

j = j*2 executes k times and the terminating condition executes k+1 times where

2^(k-1) < n < 2^(k)

i.e.

the upper bound of the loop is log n to the base 2 or log (n+1) to the base 2

The loop therefore is

O(log (n+1) )