# Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning

In the book

Introduction to Algorithms (3th edition) chapter 7

the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$ as the worst-case happens when the partitioning has one subproblem with $$n-1$$ elements and one with $$0$$ elements.

Now, they they guess $$T(n)=\Theta(n^2)$$ for the substitution method. I don't understand this, why choose $$\Theta(n^2)$$? I personally would have chosen $$\Theta(n)$$, which is wrong.

With the help from a fellow friend I came to the following conclusion:

We know that we have to make $$n-1,n-2, \dots, 2,1 \text{ comparisons}$$

So when looking at the arithmetic series $$\sum_{i=1}^n k = \Theta(n^2)$$

We can conclude that $$T(n) = \Theta(n^2)$$.

With the substitution method, you add up $$\Theta(n) + \Theta(n-1) = ... + \Theta(1)$$, roughly n times $$\Theta(n)$$, therefore about $$n^2$$.
If you have a sum that isn't as simple as this one here, you can just give a rought upper and lower bound: There are in the worst case n/2 partitions each taking n/2 or more comparisons (lower bound $$n^2/4$$) but also n partitions taking at most n comparisons (upper bound $$n^2$$).