Mathematical Proof of the Solution


Complexity is total number of time inner loop runs.

  1. 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).

  2. Now we know , inner loop runs k == log(N) time.

  3. 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

  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

  2. Simplification
    2N(2N-1)/2N = (2N-1)
    which is O(n)


Wow! such a nice explaination, it has totaly given me a clear concept.
thank u so much