Find the total number of comparisons:

Question

Find out total number of comparisons made in the execution of the loop for any n > 0 in term

of CEILING or FLOOR function.

int j, n;

j = 1;

while (j <n)

j = j*2;

I'm not able to understand about the function I should use in this case(j<n).

Answer 1

Suppose there are 100 inputs...

the loop will take 8 iterations:1 ,2,4,8,16,32,64,128

Suppose there are 1000 inputs...

the loop will take 11 iterations: 1,2,4,8,16,32,64,128,256,512,1025

Suppose there are 10000 inputs...

the loop will take 14 iterations: 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384

So here's performance measure as a function of N, the # of inputs

N # of iterations

100 8

1000 11

10000 14

looks logarithmic to me.....

log(N)