Position of Pivot | Left of pivot | Right of pivot | T(nleft) | T(nright) |
---|---|---|---|---|
1 | 0 | n-1 | T(0) | T(n-1) |
2 | 1 | n-2 | T(1) | T(n-2) |
3 | 2 | n-2 | T(2) | T(n-3) |
--- | --- | --- | --- | -- |
--- | --- | --- | --- | --- |
--- | --- | --- | --- | --- |
n-2 | n-3 | 2 | T(n-3) | T(2) |
n-1 | n-2 | 1 | T(n-1) | T(1) |
n | n-1 | 0 | T(n-1) | T(0) |
The number of comparisons for first call on partion:
Assume left_to_right moves over k smaller element and thus k comparisons.
So when right_to_left crosses left_to_right it has made n-k+1 comparisons.
So first call on partition makes n+1 comparisons.
The average case complexity of quicksort is:
{T(n) = comparisons for first call on quicksort + Σ1<=nleft,nright<=n[T(nleft)+T(nright)]}
=(n+1) + 2[T(0) + T(1) + T(2) + ----T(n-1)/n.....(1)
So,
nT(n) = n(n+1) + 2[T(0) + T(1) + T(2) + --- +T(n-2) + T(n-1)] .......(2)
(n-1)T(n-1) = (n-1)n + 2[T(0) + T(1) + T(2) + --- +T(n-2)] ........(3)
Subtracting equn(3) from equn(2):
nT(n) - (n-1)T(n-1) = [n(n+1) - (n-1)n] + 2T(n-1)
= 2n + 2T(n-1)
nT(n) = 2n + (n-1)T(n-1) + 2T(n-1)
= 2n +(n+1)T(n-1)
T(n) = 2 + (n-1)T(n-1)/n
The recurrence relation obtained is:
T(n)/(n+1) = 2/(n+1) + T(n-1)/n
Using the method of substitution:
T(n)/(n+1) = 2/(n+1) + T(n-1)/n
T(n-1)/n = 2/n + T(n-2)(n-1)
T(n-2)/(n-1) = 2/(n-1) + T(n-3)/(n-2)
T(n-3)/(n-2) = 2/(n-2) + T(n-4)/(n-3)
-------------------------------------
-------------------------------------
T(3)/4 = 2/4 + T(2)/3
T(2)/3 = 2/3 + T(1)/2
T(1)/2 = 2/2 + T(0)
Adding both sides
T(n)/(n+1) + [T(n-1)/n + T(n-2)/(n-1)+------+ T(2)/3 + T(1)/2]
= [T(n-1)/n + T(n-2)/(n-1)+------+ T(2)/3 + T(1)/2] + T(0) + [2/(n+1) + 2/n + 2/(n-1) + ----- + 2/4 + 2/3]
Canceling the common terms:
T(n)/(n+1) = 2[1/2 + 1/3 + 1/4 +-------- +1/n + 1/(n+1)]
= 2Σ2≤k≤(n+1)(1/k)
[=2Hk, Hk is called the kth harmonic number]
≤2∫ dk/k for k varyfing from 2 to (n+1)
2[loge(n+1) - loge2]
Hence, T(n) = O([(n+1) 2[loge(n+1) - loge2]
=O(n log n)
Comments
Post a Comment