CSC263 Solving the recurrence relation for quicksort
Felipe Vicencio-Heap July 13, 2020
Recall that we found that the time that quicksort takes to run on an input of size n, T′(n), satisfies the following recurrence relation in expectation:
T′(0) = 0
T′(1) = 0
′ n1 ′ ′
i=1
That is, we sum over all possible values of the pivot (i), multiplying the prob- ability of a particular pivot and the number of comparisons performed for the pivot. Since we assume the input array is distributed uniformly at random, both L and G are also distributed uniformly at random.
First we distribute the sum and factor out constants:
1 n
T′(n) = n − 1 + n
Here we have to notice that as i goes from 1 to n, both T′(i−1) and T′(n−i) go from T ′(0) to T ′(n − 1), albeit in different orders. Since T ′(0) = 0 we can drop this term and get
2 n−1
T′(n)=n−1+ T′(j)
n
j=1 Next we’ll write down T ′(n) and T ′(n − 1):
2 n−1
T′(n)=n−1+ T′(j)
n
j=1
2 n−2
T ′(j) j=1
T (n)=
(n·(n−1+T (i−1)+T (n−i))
i=1
(T′(i − 1) + T′(n − i))
T ′(n − 1) = n − 2 + 1
n−1
We can almost subtract T′(n−1) from T′(n) to cancel most term, if it weren’t for the multiplicative term. Instead we compute
nT′(n) − (n − 1)T′(n − 1)
n−1 n−2
(1) = n(n − 1) + 2 T ′(j) − (n − 1)(n − 2) − 2 T ′(j) (2)
j=1 j=1 = 2(n−1)+2T′(n−1)
Which gives us the recurrence
nT′(n) = (n + 1)T′(n − 1) + 2(n − 1)
We’ll divide both sides by n(n + 1) and re-write the recurrence T′(n) =T′(n−1)+2(n−1)
(n+1) n n(n+1) Let A(n) = T′(n) so that we can write
n+1
A(n)=A(n−1)+ 2(n−1) n(n+1)
Note that
Now by unrolling this reccurence we can try to solve
(3)
A(0) = T′(0) = 0 1
A(n)=n 2(i−1) (4)
= 2 n 1 − 2 n 1 (5) i+1 i(i+1)
i=1 i=1
n+11 n 1 1
=2−2(− ) (6) iii+1
i=2 i=1
Note that the second term is a telescoping series, which collapses down to
1−1 n+1
NowwecanintroducetheHarmonicseriesH(n)=1+1 +1 +…+1,so 23n
A(n) = 2(H(n+1)−1)−2(1− 1 ) n+1
A(n)=2H(n+1)−4+ 2 n+1
Since we know H(n) ∈ O(logn) we can conclude that A(n) ∈ O(logn) thus T′(n) ∈ O(nlogn)
2
i(i+1) i=1