Take the 2-minute tour ×

I have problems to give the right time complexity in O notation for the following loop:

k := 0
for i := 0 to N
   for j := k to M
     // something
   k = k + 1

Where N = M. Without the modified starting value of j of the inner value this would be of course O(N * M), but with the decreasing running time of the inner loop in every step of the outer loop I am quite confused. How can this be approached?

share|improve this question
add comment

4 Answers

When M >= N, decreasing by one makes the inner loop run (2*M+N)/2 on the average, so the overall complexity remains O(M*N). When N > M, the outer loop runs M times, and then becomes an empty operation for the remaining N-M iterations, because once k reaches M, the inner loop executes zero times. So the overall result is O(M*min(M,N))

share|improve this answer
@MikeNakis Well, we've got very different answers :) Mine came out essentially as O(M^2), not O(N*M) –  dasblinkenlight Jan 14 '12 at 0:49
wh00ps, I must have read his answer wrong. He is not even saying O(N*M). He is saying O(M). –  Mike Nakis Jan 14 '12 at 1:58
@MikeNakis But he is talking about the complexity of the inner loop, not the overall complexity. The implication is that since the inner loop is O(M) and the outer is O(N), the overall complexity must be O(N*M). This is correct when the values of N and M are close to each other, but when one is significantly smaller than the other, the complexity is different. –  dasblinkenlight Jan 14 '12 at 2:16
Yes. So I read his answer correctly the first time. Oh well, next time I should remember to stay away from anything related to programming when my mind is not clear. –  Mike Nakis Jan 14 '12 at 7:34
add comment

The decreased running time isn't enough to change the time complexity- the inner loop still runs in O(M).

share|improve this answer
add comment

I want to try.

The 'something' would be done N*M if there was no 'k'.

How many 'something' would not be done because of k ?

First iteration, there will be no removed 'something'. Second iteration, there will be one removed. Third, two. So, the number of 'something' that would not be done because of k is equal to sum from 1 to M.

Sum from 1 to M is equal to M*(M+1)*(1/2). So :


share|improve this answer
add comment

actually it's O(N*(N+1)/2)... why ??

it's looks like this...

1 2
1 2 3
1 2 3 4

gauss summation.. and because, asymptotic notation ignore constant value, then it will be O(N*N)...=)

share|improve this answer
add comment

Your Answer


