This answer should be N * log(N)


#1

Is anyone monitoring this discussion. Why is this not n * log(n)


#2

I do agree it should be N*log(N) since J is really run N times. But why log(N) iterations for i is not counted?
N(j)*log(N)(i)


#3

If you see it closely the max the algo can run is 2N.

If you analyze first few runs it will go like N + N/2 + N/4 + N/8 …

Hence, the answer is O(N)


#4

log(N) orderations for i is counted but the total is O(log(N)) + O(N) => O(N), not O(log(N)) * O(N) => O(N log N).

Ask yourself – which statement in the program is actually executed N log N times?

It’s not the comparisons/assignments in the outer loop (which are O(log N)). The comparison/assignments in the inner loop are executed N times on the first iteration N/2 the second, etc. which is O(N) overall.

So you have O(log N) statements + O(N) statements => O(N).


#5

why we are adding N+(N/2+N/4)
why we are not multiplying it I do not understand please anyone help me


#6

// i will not tell the soln but a nyc approach

I see people having trouble with finding time complexity with nested loops like what to do multiply or add , lets see …

Every problem can be computed by addition method , they are actually same .
eg. for (i = n/2; i <= n; i++)
{
for (j = 2; j <= n; j = j * 2)
{
k = k + n/2;
}
}
In the above problem we see that the outer loop has complexity O(n)
and the inner loop has Olog(n), so the total time complexity is O(nlogn) which is correct
which can also be deduced in the following manner :
for each iteration of outer loop the inner loop gets executed fixed number of time (logn times)
so total time complexity is :
logn + logn +logn +…+logn = ‘n’ times logn = nlogn
(everything good till now)

now our problem

for (int i = N; i > 0; i /= 2)
{
for (int j = 0; j < i; j++)
{
count += 1 ;
}
}
here we see outer loop is logn and inner loop is ‘n’ so time complexity is nlogn , which is WRONG.
because for each iteration of outer loop the number of times inner loops executes is not fixed but depends on that outer loop since here the condition in inner loop is (j=0; j<i; j++) but in last example it was (j=2 ; j<=n ; j=j*2) .
we see " j<i " so we know that number of times inner loop runs is not fixed (which in previous example was fixed) (try to dry run the code) so we cannot find time complexity by multiplying the outer and inner
loop’s complexity but we can find it by using a different application of multiplication i.e ADDITION

4*3 = 3+3+3+3
nlogn= logn+logn+logn…+logn (n times)

now : for each iteration of outer loop the inner loop gets executed some (not a fixed value) number of
times
see other comments for full maths derivation of GP and all.

remember we are not neglecting the outer loop in the same way in 4*3 = 3+3+3+3 we are not neglection the 4 but adding 3 four times.

If you still have doubts , read a basic programming book or watch some video , read the permutation and ‘counting number’ chapters in 11/12 maths book.


#7

See the Outer Loop runs for log(N) times… i hope that’s clear.

Now, for the Inner Loop i goes like N, N/2, N/4, N/8 … log(N) terms (we saw from Outer loop)

so… N(1+1/2+1/4+ … log(N) terms) ; Now you may or may not calculate the coefficient using GP(Geometric progression) ; time-complexity will come O(N)

PS: I know this is a bit clumsy explanation, but this forum got other great explanations too :grin:


#8

Answer is O(N) as outer loop doesn’t consist of any assignment operation.


#9

Can some one please explain this with some Video and provide the link here. I am confused in its time complexity.