Alogorithms exercise

Question

I would like to know the complexity of this algorithm, I am a bit confused in the notation.

for(int i=0; i<N; ++i) 
    for(int j=M-1; j>=i; --j) 
        ++x

The answers are:

O(min(N,M))
O(N*M)
O(N+M)
O(max(N,M))

Time complexity is: `O(N) * O(M)`. In other words: `~O(n^2)` — Shyam Baitmangalkar, Jan 05 '21 at 06:06
What do you think it is, and why do you think that? Give us your thoughts, and show that you at least tried. — Andreas, Jan 05 '21 at 06:08

score 1 · Answer 1 · answered Jan 05 '21 at 06:06

Short answer: O(N*M)

Explanation: First, the outer loop is executing N times no matter what. The inner loop will be executed M times in the first iteration, M-1 times in the second iteration, and so on. This is an Arithmetic progression with a sum of d*(a1+an)/2 Which is 1(M+1)/2 which is O(M). Multiply O(N) and O(M) will give you O(N*M).

Alogorithms exercise

1 Answers1