Big O analysis of a sorting algorithm that counts smaller elements

Question

How do I prove the runtime of an algorithm with Big O notation? I don't know much about O notation, I just I know how to compare sets of functions with each other and I'm also familiar with the master theorem.

But how do I do this? Is it just $O(n^2)$ because there are $2$ loops? That doesn't sound right. The loop in COUNTSMALLER doesn't have else so it's less expensive than the other one. I just know that cnt <- 0 is $O(1)$ but I don't know exactly about the loops. Am I supposed to do something with $T(n) = a T(n/b) + f(n)$? I could do that if you give me $a$ and $b$ but I have to idea how to get those or if this even makes sense.

This algorithm doesn't terminate if some elements are equal btw, I guess we can assume that all elements in the array $A$ are unique.

SORT(A)
1 i <- 1
2 while i < len(A) do
3    j <- COUNTSMALLER(i, A) + 1
4    if i = j then
5       i <- i + 1
6    else
7       A[i] <-> A[j]
8    end if
9 end while


COUNTSMALLER(i, A)
1 cnt <- 0
2 for j <- 1 to len(A) do
3    if A[i] > A[j] then
4      cnt <- cnt + 1
5    end if
6 end for
7 return cnt    

```

Answer 1

The big-$O$ analysis of an algorithm consists of two part in practice.

• A quick and rough estimate, which works often.
• Rigorous analysis as well as refinement when necessary.

---

We assume that the algorithm works. That means on any valid input (i.e., no duplicate numbers), it returns the correct result in finite time.

As a first guess, the time-complexity is probably $O(n^2)$ since there is a nested loop, where each loop seems contributing a factor of $n$.

---

Now let us take a closer look.

It takes $O(n)$ time to run COUNTSMALLER(i, A).
So, it takes $O(n)$ time to run line 3 to line 8, the loop body of the while loop in SORT(A) once.

Now the question is how many times will that loop body be run? Each time the loop body is run, either $i$ will increase by $1$ or one more position of the A stores the expected value. Since $i$ can increase at most $n$ times and there are $n$ position in A, the loop body runs at most $2n$ times. Hence it takes $O(n\times n) = O(n^2)$ to run the while loop in SORT(A).

It takes less time comparatively to run all other code such as line $1$. Hence the time-complexity is $O(n^2)$.