0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

Please comment if I can improve my answer in any way.

$\endgroup$
1
$\begingroup$

With the substitution method, you add up $\Theta(n) + \Theta(n-1) = ... + \Theta(1)$, roughly n times $\Theta(n)$, therefore about $n^2$.

Note that this is for an initial guess - to help you make a guess your maths doesn't have to be strict. To prove it, you need to be strict.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.