Why isn't it O(nlogn)

#1

Someone said
" try to think this way:
for the first iteration of the outer loop, the inner loop need to run N times, the second iteration of the outer loop, the inner loop need to run N/2 times, third iteration, N/4 times, so add them up, you’ll get N + N/2 + N/4 + … + 1, which is 2N-1, and asymptoticly O(N) "

I can give a similar argument for this loop
for(i = 0; i < n; i ++) {
for(j = 0; j < n; j++) {
}
}

The inner loop runs n times for the first iteration, then again n times for the second iteration, and so on… so its n + n + n… = O(n)

:frowning:

#2

For your question:
for(i = 0; i < n; i ++) {
for(j = 0; j < n; j++) {
}
}
For 1st iteration : N times
For 2nd iteration : N times
…
For N iteration : N times

Sum up all iterations = N + N + … + N
= N(1+1+…+1 ( N times) ) = N^2
Therefore, O(N^2) :slight_smile:

#3

The series summation of the outer loop is not O(logN).The series is 1 + 1/2 + 1/4 + 1/8 … rather then 1+1/2+1/3…So the r of the infinite series will be 1/2.

#4

Cause the 2nd loop is dependent on the first loop so we need to unroll the loops and solve it ,we cannot multiply it directly.

#5

ishansoni22, for nested loop example, why isn’t the time complexity = O(n^2)?
You only took into account the inner loop. What about the outer loop? I think that’s where I’m confused about for the original question too. I thought outer loop is (logn) and inner loop is (n), therefore it should be (nlogn), where is my logic incorrect?

#6

I think what ishansoni22 meant was O(n^2) because we can clearly see it has inner loop and takes N times for inner loop and N times for outer loop

#7

Thanks Devansh. Your reply makes everything clear now.