Mathematics behind NESTED_CMP3

programming
Tags: #<Tag:0x00007f1822cabae8>

#1

SO.For those who didn’t get in first go. They can understand it like this:

First of all, look at the outer loop. You can see it iterates until i < 1 or i = 0. So, outer loop executes for values for i = N, N/2, N/4 … N/2^k (executing k number of times)

N/2^k < 1

N<2^k

k>log(N)

so, outer loop executes logN times.

Now, looking at inner loop. First of all, it executes for N times, then N/2 times then N/4 times until it reaches 1. Basically, executing logN times.

So, time complexity will be N + N/2 + … logN terms.

By Geometric progression:
a=N, r= 1/2, n= logn (Remember logn has base 2)
Also, using a^logb = b^loga and log2 is 1.

N((1- (1/2)^logN)/(1-1/2)) = 2N(1-(1^logN)/(N^log2)) = 2N(1-1/N)=2(N-1) = 2*N = O(N)

So, time complexity is O(N)


#2

Hey, Thanks for the explanation :grin:

What if we just ignore the coefficient in N(1 + 1/2 + 1/4 + … log(N)terms) no need of a evaluation using GP ; time complexity will be O(N)