5
$\begingroup$

I have been taught that QuickSort has the following recurrence equation in the best case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

where $c \in \Theta(1)$ and $c \cdot n \in \Theta(n)$. As well for the general case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q) + c \cdot n & \text{if } n>1 \end{cases}$

Moreover, the algorithm used in the lecture was the following:

Procedure QuickSort(A[p,...,r])
    if p < r
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)

As you can see, the recursive calls don't take care of the pivot element $q$. I understand this occurs as Partition moves elements around until the pivot is where it should be is the array ordered. The following is the Partition algorithm:

Function Partition(A[p,...,r], p, r)
    x = A[r]
    i = p-1
    for j = p to j = r-1 do
        if A[j] <= x
            i = i+1
            Exchange(A[i], A[j])
    Exchange(A[i+1], A[r])
    return i+1

My question is: Why do the recurrence equations assume the algorithm takes all the elements of the array (let it be $n$) if the actual algorithm only takes $n-1$ elements?

Why can't it be the following?

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n-1}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

Or, more generally, this one?

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q-1) + c \cdot n & \text{if } n>1 \end{cases}$

Improve this question
$\endgroup$
10
  • $\begingroup$ You're right, your recurrence is the correct one. But both have the same solution and the second is more cumbersome, so the first is often used. $\endgroup$
    – Yuval Filmus
    Mar 21, 2016 at 6:54
  • $\begingroup$ @YuvalFilmus I guess they use the first one as it yields the same result and it's easier to prove. You see, I made the proof of the second one just to see if it yielded the same result... Indeed, it does, but it's a bit more difficult. $\endgroup$
    – logo_writer
    Mar 21, 2016 at 7:07
  • $\begingroup$ How would you prove the first one? It's incorrect. It should be impossible to prove. $\endgroup$
    – Yuval Filmus
    Mar 21, 2016 at 7:07
  • $\begingroup$ @YuvalFilmus I assume you meant by "first one" the first that appears in my question. $\endgroup$
    – logo_writer
    Mar 21, 2016 at 7:09
  • 1
    $\begingroup$ "as it takes Θ(n) time, can be represented with any function - for instance, c⋅n" -- but this is not always true! It's an admissible simplification if you are only after $\Theta$-bounds, though. But well, now your sentence is correct at least. $\endgroup$
    – Raphael ♦
    Mar 21, 2016 at 22:12

2 Answers 2

Reset to default
4
$\begingroup$

When you're looking at the behaviour of the algorithm as $n\to\infty$, the difference between $n$ and $n-1$ becomes negligible. The simpler form is easier to deal with and it gives the same answer.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Also, assuming that $T$ is monotone (which can be proved by induction), the formula gives an (almost tight) upper bound on the running time. $\endgroup$
    – Yuval Filmus
    Mar 21, 2016 at 7:08
  • 1
    $\begingroup$ Now I understand. As with $O(n+c) = O(n)$, in this problem it's seen that taking care of the real partition is almost negligible as $n \to \infty$. And so, the complexity is the same. $\endgroup$
    – logo_writer
    Mar 21, 2016 at 7:19
  • 2
    $\begingroup$ "the difference between n and n−1 becomes negligible" -- note that this is only an a posteriori argument. Once we know the solution of the precise recurrence is in $\Theta(n \log n)$ we can make it, but not before. For instance, $(n-1)! \in o(n!)$; we need a suitable upper bound at least in order to exclude too-fast-growing functions. $\endgroup$
    – Raphael ♦
    Mar 21, 2016 at 9:20
4
$\begingroup$

As well for the general case: [recurrence with $q$]

Note how $q$ remains a free variable here; that's bad. It's not the same $q$ for every recursive call, and either way you can not really solve the recurrence. You need to let $q$

  • be $0$ or $n - 1$ for the worst case,
  • be $n/2 \pm 1$ for the best case, or

  • sum over $\sum_{q=0}^{n-1}$ and take the average by multiplying with $\frac{1}{n}$ for the average case (under the random permutation model).

    Note that more involved arguments are needed to see that this last one is actually correct, in particular that the recursion maintains the random model.

As such, the form with $q$ is an intermediate step only.

Why can't it be the following [with $n-1$ instead of $n$]?

It can, and it should. However, the recurrence may be easier to solve if you use $n$ instead of $n-1$. The simplification can be justified if you

  • are only interested in asymptotics and

  • establish that

    $\qquad\displaystyle \frac{T(n)}{T(n-1)} \in O(1)$

    as $n \to \infty$. This is the case if $T$ is "smooth" and does not grow too fast.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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