Analysis of Quicksort
T (n) = max ( T (q) + T ( n-q ) + Q (n)
), 1 £ q £ n-1
Guess T (n) = c n2
T (n) £ max ( c q2 + c ( n-q )2
) + Q (n) :: 1 £
q £ n-1
= c max ( q2 + ( n-q )2 ) + Q
(n) :: 1 £ q £
n-1
We can show that:
q2 + ( n-q )2 = q2 + n2 -
2 n q + q2 = n2 - 2 n q + 2 q2 = f (q)
f ' (q) = 4 q - 2 n = 0 Þ q = n/2
max ( q2 + ( n-q )2 ) £
( 12 + ( n-1 )2 ) = n2 - 2 (
n-1 ) :: 1 £ q £
n-1
T (n) £ c n2
- 2 c ( n-1 ) + Q (n) £
c n2 Since the 2 c ( n-1 ) and Q (n)
cancel out.
We swap firts for arbitrary value, x. So rank (x) = i :: i = 1 ...
n is equally probable. Or P { rank (x) = i } = 1/h.
| Rank = 1 |
X |
| |
|
|
|
|
|
|
|
| Rank = 2 y < x |
Y |
| |
|
|
|
|
|
|
X |
| Rank = i |
|
|
i
- 1 ................ Ü |
| |
|
|
P { low side = i } = { 2/h if i = 1 or 1/h if i = 2 ... n-1 }
T (n) = cost of Randomized-Quicksort
T (1) = Q (1)
Partition returns q,
| T (n) = 1/n [ T (1) + T ( n-1 ) + |
n-1
å
q = 1 |
( T (q) + T ( n-1 ) ) ]
+ Q (n) |
|
T (1) = Q (1) but by worst-case Q
(n2) so 1/n ( T (1) + T ( n-q )) = 1/n ( Q
(1) + Q (n2) ) = Q
(n)
| T (n) = |
n-1
1/nå
q =
1 |
( T (q) + T ( n-q ) )+ Q
(n) = |
|
n-1
2/nå
q = 1 |
T (q) + Q
(n) |
|
Assume T (n) £ a n lg n + b
| T (n) £ |
n-1
2/nå
q =
1 |
( a q lg q + b ) + Q
(n) = |
|
n-1
2 a/nå
q = 1 |
q lg q + 2 b/n ( n-1
)+ Q (n) |
|
** See the book for a proof.
T (n) £ 2 a/n ( n2/2 lg n - n2/8
) + 2 b/n ( n-1 ) + Q (n)
£ a n lg n - a/4 n + 2 b + Q
(n)
= a n lg n + b + ( Q (n) + b - a n/4
) Note: a/4 big enough a n/4 ³ Q
(n) + b
£ a n lg n + b
|
