# Time complexity of a nested loop where the inner value is decreased in every step

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?

-

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))`

-
@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

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

-

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 :

O((M*N)-M(M+1)*1/2)

-

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

it's looks like this...

``````1
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)...=)

-