Mathematical Proof of the Solution


#1

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)


#2

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