# Quick Sort worst case, why $n^2$?

I have a very hard time understanding this proof:

$$T(N) = T(N-1)+cN$$

$$T(N-1) = T(N-2)+c(N-1)$$

$$T(N-2) = T(N-3)+c(N-2)$$

$$\vdots$$

$$T(2) = T(1)+c(2)$$

$$T(N) = T(1)+c\sum_{i = 2}^{N} i = O\big(N^2\big)$$

I can see that we have $$T(N-1)$$ and then $$T(N-2)$$ and so forth because the array to check shrinks by one each time. The $$cN$$ is what exactly? Why does it get decremented by one, two etc.? And how does the summation equal $$n^2$$ at the end, it doesn't make any sense to me. I see nowhere that $$n$$ is getting multiplied by itself sinse it results in $$n^2$$.

• It takes linear time $O(N)$ to compare every elements with pivot point. Nov 9 '18 at 11:49

the $$ck$$ is the additional complexity you get by adding another element you need to sort. For example, as soon as you "sorted" 1 object, you just need to add the complexity for $$N-1$$, hence $$T(k)=T(k-1) + ck$$ where c is some constant. the $$k$$ on the righthand side comes from sorting the $$k$$'th additional input, which has complexity $$k$$, (since it needs to be shuffled all through the sequence in the worst case).
Hence you arrive on the bottom formula including the sum $$\sum_{i=1}^N ci$$. This is, by the formula for arithmetic series: $$\sum_{i=1}^N ci= cN(N+1)/2=cN^2/2 + cN/2$$ hence we get as complexity $$O(N^2)$$.
• But why do we decrement k then c(k -1) and so on? Isn't the T(n-1) what tells us the size of the array? And how can $cN^2 /2 + cN /2$ make $n^2$? $10^2 / 2$ does not make $10^2$?
• and what is $T(N-1)$? it is $T(n-2)+c(n-1)$, and since you do not know $T(n-1)$, you just keep going until you know $T(n-i)$, which happens latest at $T(1)=0$, which then allows you to give a closed formula. if you have problems with such arguments, i recommend you revise induction! Nov 9 '18 at 12:01
• you really need to revisit $O$ notation! I never said it is the same! i said it has the same order! please be sure you know your definitions before you ask a question, that is really frustrating, I feel like somebody asks me why people drink water without even knowing what water is! Nov 9 '18 at 12:21