Can anyone explain how the complexity of option C is O(logn).
C is increasing as 1 ,2 ,4, 8, 16… which is basically a log_2_(n)
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)
loop became false @ i>n
therefore k=log n
and out of the 4 staement logn is the lowest time used ,so efficient
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)