Java Reference
In-Depth Information
Because the cost to quicksort
N
items equals
N
units for the partitioning
step plus the cost of the two recursive calls, we need to determine the average
cost of each of the recursive calls. If
T
(
N
) represents the average cost to quick-
sort
N
elements, the average cost of each recursive call equals the average—
over all possible subproblem sizes—of the average cost of a recursive call on
the subproblem:
The average cost of
a recursive call is
obtained by averag-
ing the costs of all
possible subprob-
lem sizes.
T
()
T
()
T
() …
TN
1
+
+
+
+
(
-
)
TL
()
=
TR
()
=
---------------------------------------------------------------------------------------
(8.4)
N
Equation 8.4 states that we are looking at the costs for each possible subset
size and averaging them. As we have two recursive calls plus linear time to
perform the partition, we obtain
T
0
()
+
T
1
()
+
T
2
() …
+
+
TN
1
(
-
)
⎛
⎞
TN
()
=
2
---------------------------------------------------------------------------------------
+
N
(8.5)
⎝
⎠
N
To solve Equation 8.5, we begin by multiplying both sides by
N,
obtaining
The average run-
ning time is given
by
T
(
N
)
. We solve
Equation 8.5 by
removing all but the
most recent recur-
sive value of
T
.
()
…
NT N
()
=
2
T
0
(
()
+
T
1
()
+
T
2
+
+
TN
1
(
-
)
)
+
N
2
(8.6)
We then write Equation 8.6 for the case
N
- 1, with the idea being that we can
greatly simplify the equation by subtraction. Doing so yields
()
…
(
N
1
-
)
TN
1
(
-
)
=
2
T
0
(
()
+
T
1
+
+
TN
2
(
-
)
)
+
(
N
1
-
)
(8.7)
2
Now, if we subtract Equation 8.7 from Equation 8.6, we obtain
NT N
()
-
(
N
1
-
)
TN
1
(
-
)
=
2
TN
1
(
-
)
+
2
N
1
-
We rearrange terms and drop the insignificant -1 on the right-hand side,
obtaining
Once we have
T
(
N
)
in terms of
T
(
N -
1)
only,
we attempt to
telescope.
NT
()
=
(
N
1
+
)
TN
1
(
-
)
+
2
N
(8.8)
We now have a formula for
T
(
N
) in terms of T(
N
- 1) only. Again the idea is to
telescope, but Equation 8.8 is in the wrong form. If we divide Equation 8.8 by
N
(
N
+ 1), we get
()
N
1
TN
TN
1
(
-
)
2
N
1
=
+
-------------
---------------------
-------------
+
N
+
Search WWH ::
Custom Search