Explain Option C


#1

Can anyone explain how the complexity of option C is O(logn).


#2

C is increasing as 1 ,2 ,4, 8, 16… which is basically a log_2_(n)


#3

In option D,’ i’ is repeatedly divided by 2. At some point, ‘i’ will become 0. After that ‘i/2’ will still be 0. So, I think that it is an infinite loop. (condition : i > -1)


#4

i=1,2^1,2^2,2^3…let 2^k
loop became false @ i>n
i.e, 2^k>n
therefore k=log n
and out of the 4 staement logn is the lowest time used ,so efficient


#5

i starts from 1 and then increments as follows :
i = 1
i = 2
i = 2^2
i = 2^3
.
.
.
i = 2^k where k is an arbitrary integer.
the upper limit of loop is i < n.
=> 2^k = n-1
for calculating time complexity we use Apriori analysis hence use approximations
therefore using approximation here
2^k = n
Taking log (with base 2) on both sides , we get :
=> log (2^k) = log n
=> k log 2 = log n
=> k = log n --(1)
So , one iteration time complexity is O(1) then for k iterations time complexity will be O(k).
Using equation (1), we get :
T(n) = O(log n)