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

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.

## 2 Answers

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

• Thanks but this is confusing.Can you explain to me in a lower level.What does it mean by "algorithm terminates with an entry data of size n" ? what is this entry.I did not understand anything below this :) – techno Jul 3 '15 at 6:35
• The execution time has generally a direct link with the size of the data it has to deal with. I mean, here you enter a list to sort : it will take more time if your list contains $150000$ elements ($n=150000$) than if it only has $10$ ($n=10$). We don't calculate actually a running time, but rather a number of operations needed to get the result – BusyAnt Jul 3 '15 at 6:39
• okay............ what is p(n) ? – techno Jul 3 '15 at 6:40
• I noted $p(n)$, but you never use it in a concrete exercise. It is just a simple expression depending of $n$ that you will put in the $\mathcal O$, or the $\Theta$, or the $\Omega$. For instance, if you find $\mathcal C(n) = 2n^2-\frac{n}{5}+6\sqrt{n}$, you will say that $\mathcal C(n) = \Theta(n^2)$, because when $n \rightarrow \infty$, $\mathcal C(n) \sim n^2$ – BusyAnt Jul 3 '15 at 6:45
• For insertion sort the worst case running time is given by an² +bn+c .So we can represent running time by O(n² ) . ie: we ignore the terms with low coefficient. – techno Jul 3 '15 at 6:52

In each partition, the pivot element is always the smallest element. therefore each partition will produce two subarrays. the first subarray contains only one element(the smallest element) and this element is in its correct position. the second subarray contains the remaining elements. so the running time recurrence will be T(n) = T(n-1) + n. thus T(n) = Ө(n^2)