Running Time of Sorting Algorithm

Question

Determine the asymptotic running time of the sorting algorithm maxSort.

Algorithm maxSort(A)
Input: An integer array A
Output: Array A sorted in non-decreasing order

1. for j <- n-1 down to 1 do
2.     m <- 0  
3.     for i = 1 to j do  
4.         if A[i] > A[m] then m <- i
5. exchange A[m], A[j]

Can you say anything about the "best-case" function $B_{maxSort}(n)$?

---

With a question like this, what is the way to tackle it? I have tried counting number of executions per line, but I can't translate it into asymptotic notation. My intuition is that it has something to do with $n^2$ due to the nested for loop, but I am not sure about this.

Answer 1

When the indexes of the for loops depend on each other you can think like this:

When the index of the outer for loop takes its first value how many times is the inner for repeated? What about when the index of the outer for takes its second value? ... What happens when the index of the outer for takes its last value?

In your case: When $j = n-1$, $i$ is repeated $n-1$ times. When $j = n-2$, $i$ is repeated $n-2$ times. ... When $j = 1$, $i$ is repeated $1$ time.

In total, the inner for loop is executed $(n-1) + (n-2) + ... + 2 + 1 = \dfrac{n}{2} * n = n^2$ times. Therefore the complexity is $O(n^2)$.

The best case is obviously when the matrix is already sorted.

Answer 2

I find the most useful phrase when trying to quickly understand the asymptotic behavior of an algorithm (and likewise in quick dimensional analysis of physical problems) is "suppose we have twice as many..."

In the above problem, suppose we have twice as many elements. Then the outer loop will run twice as many times. But j is proportional to n, so the inner loop will also run twice as many times per run. Therefore the inner loop will run four times as often in total. So that's O(n^2).