Big-O CS Question

Question

Approximate the runtime of the following code fragment, in terms of n: Write your answer in a format such as "O(N^2)" or "O(N log N)" (without the quotes).

int sum = 0;

int j = 1;

while (j <= n) {

sum++;

j = j * 2;

big-oh: ?

Answer 1

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

Answer 2

it's linear

O(n)