gotchaMinor
Why does the recurrence equation for QuickSort consider all the elements in the array?
Viewed 0 times
whytheelementsallarrayconsiderrecurrencequicksortfordoes
Problem
I have been taught that
$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:
As you can see, the recursive calls don't take care of the pivot element $q$. I understand this occurs as
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}$
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+1My 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.