HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Why does the recurrence equation for QuickSort consider all the elements in the array?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whytheelementsallarrayconsiderrecurrencequicksortfordoes

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#54713, answer score: 4

Revisions (0)

No revisions yet.