Analysis of Algorithms : An Active Learning Approach

3.7 QUICKSORT 93

This is a very complicated form of recurrence relation because it depends
on not just one smaller value of A, but rather on every smaller value for A.
There are two ways to go about solving this. The first is to come up with an
educated guess for the answer and to then prove that this answer does satisfy
the recurrence relation. The second way is to look at the equations for both
A(N) and A(N
1). Those two equations differ by only a few terms. We now
computeA(N)N and A(N
1) (N
1) to get rid of the two fractions.
This gives

Now, we subtract the third equation above from the second and simplify to get

AddingA(N
1) * (N
1) to both sides, we get

This gives our final recurrence relation:

Solving this is not difficult but does require care because of all of the terms
on the right-hand side of the equation. If you work through all of the details,
you will see the final result is A(N)
1.4 (N + 1) lg N. Quicksort is, therefore,
O(N lg N) on average.

AN()*N ()N– 1 N 2 Ai()

i=0

N–1

= + ∑

AN()*N ()N– 1 N 2 AN()– 1 2 Ai()

i=0

N–2

= ++∑

AN()– (^1) *()N– 1 ()N– 2 ()N– 1 2 Ai()
i=0
N–2
= + ∑
AN()NAN– ()– 1 ()N– 1 = 2 AN()– 1 +()N– 1 NN–()– 2 ()N– 1
AN()NAN– ()– 1 ()N– 1 = 2 AN()– 1 +N^2 – N–()N^2 – 3 N+ 2
AN()*NAN– ()– 1 ()N– 1 = 2 AN()– 1 + 2 N– 2
AN()N = 2 AN()– 1 +AN()– (^1) ()N– 1 + 2 N– 2
AN()N = AN()– (^1) () 2 +N– 1 + 2 N– 2
AN()
()N+ (^1) AN()– 1 + 2 N– 2
= ----------------------------------------------------------------------N -
A() 1 ==A() 0 0