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

# Explain Option C

**mpmaan**#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)

**dishom**#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

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