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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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)

Answer 4

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