Complexity is total number of time inner loop runs.
-
Inner loop runs for “i” number of time. Value of “i” in sequence until it stops is
N; N/2; N/4 ; N/8 … so on until last loop runs.
This can be generalized as N/(2^k) where k = 0 for first run.
Last time inner loop runs is when “i” == 1 , therefore to calculate value of k for last run, we do
(N/2^k) = 1 which implies, k = log(N). -
Now we know , inner loop runs k == log(N) time.
-
Finding total number of iterations of inner loop
sum of : N/(2^0) + N/(2^1) + N/(2^2) + N/(2^3) + …N/(2^k)
This represents a Geometric Progression.
It’s sum is firstTerm * ( 1 - (common ratio)^numerOfTerms)/(1- commonRatio)
first term : N/(2^0) = N
commonRatio = 1/2
number of terms = k+1
-
Therefore, sum is
N(1-(1/2)^(logN+1))/(1/2) => 2N(1-1/2N)
Using Properties:
a. base^(log(base)Value) = value
b. 2^(a+b) = 2^a*2^b -
Simplification
2N(2N-1)/2N = (2N-1)
which is O(n)