Show that running time of Quick Sort is $\mathcal O(n^2)$ when array contains distinct elements and is sorted in descending order

Question

I'm trying to study running time for various algorithms. Now I have QuickSort. How exactly is the running time of an algorithm calculated, I know how quick sort works and the Asymptontic notations. I understand that $\Theta$ Notation bounds functions above and below, Big-O above and $\Omega$ provides a lower bound.
How exactly is this running time calculated ? Can some one explain this for a noob please.

Answer 1

Consider $n$ a representative size in your program. Let's say $n$ is the length of the list you're working with.

The runnig time, or complexity, of an algorithm is the number of operations you need to do so that your algorithm terminates with an entry data of size $n$.

You also have to choose which operations you count, only multiplications, every arithmetic operation, comparsions...
The expression of complexity $\mathcal C(n)$ is generally obtained by a recursive process.

Let $p(n)$ be $n, n^3, 2^n,$ or $n\log(n)$ for example

To indicate complexity we use $3$ functions, because $\mathcal C(n)$ is not very relevant : $$\Omega(p(n)) : p(n) <_{n \rightarrow \infty} \mathcal C(n)$$ $$\mathcal O(p(n)) : p(n) >_{n \rightarrow \infty} \mathcal C(n)$$ $$\Theta(p(n)) : p(n) \sim_{n \rightarrow \infty} \mathcal C(n) $$

Answer 2

If the array is already sorted in decreasing order, then, the pivot element is less than all the other elements. The partition step takes Θ(n) time, and then leaves you with a subproblem of size n − 1 and a subproblem of size 0. This gives us the recurrence T(n) = T(n - 1) + T(0) + Θ(n). Note that: T(0) = Θ(1). So, in each level we will have n decreased by 1 and the partitioning cost is still Θ(n), that leaves us with T(n - 1) = T(n - 2) + T(0) + Θ(n) again.

Simply, we will have around n levels and on each level has a processing that costs Θ(n) time. That leads to Θ(n^2) time.