The inner loop runs for the following no of times- N, N/2, N/4, N/8 …
Hence total time complexity = N(1+1/2+1/4+1/8+…). The coefficient of N here is a GP with r<1 , hence we can use the GP sum formula to find its sum.
i.e. a/(1-r), where a is the starting term and r is the common ratio. Here it becomes 1/1-1/2 = 2.
Hence time complexity = 2*N = O(N).
Would you please explain what GP means?
Yes, I agree. What on earth is GP? Please be more considerate by explaining the fancy terms you use in the future - if people are asking questions on the topic, you can assume they don’t know what some esoteric math abbreviation is going to mean, thanks.
GP means Geometric Progression. It is the series of terms in the form a, ar, ar^2, ar^3, … ar^n.
You don’t need to calculate GP, since the complexity becomes N(1+1/2+1/4+1/8+…), you can easily omit (1+1/2+1/4+1/8+…) this part, which means the complexity is N
But the outer loop execute for log(n) times so the answer should be n*log(n).
thanks for the solution. great help.
But what about the outer loop?
Why are we only considering only the inner loop to calculate the time complexity?
The above problem has a nested loop so shouldn’t we consider both the loops?
What about the i loop that is being decremented by half every time?
So, should it not be logN*(2N). The term int the braces is the j loop complexity that guest_user_251 suggested.
so O(logNN) or O(N*logN).
yes answer should be nlogn
u r right bro…
see my answer in solution section for a in depth explanation and the answer is O(n).
similarly time complexity of outer loop is also O(N), so shouldn’t the total time complexity be O(N*N) ??
to understand the complexity look for how many times the count statement is executed!
here the two loops are dependent and not independent of each other!
the worst case time complexity is of order n and not n^2!
Hi Akash!The outer loop is considered when we take the execution time of j to be N,N/2,N/4…N/2^i.We should not multiply logn and n because the effect of outer loop has already been taken into account while calculating for the loop that deals with j.Since the inner loop variable j is dependent on the outer loop variable,this is the correct approach.Hope this helps!
Yes, I understand that inner loop complexity is O(n) but outer loop will run for log(n). So multiplying their complexity should give n*log(n)