be the time to sort a list of n elements using
the recursive version of insertion sort. This time includes
time for the recursive call to sort the first n-1 elements,
plus the time to insert the last element into this sorted sequence
using a loop like that in lines 2-8 of the insertion sort algorithm on Page 8.
This loop takes at most n-1 iterations, requiring 
time, so we have:
When the array is reverse-sorted to begin with, this loop proceeds all the
way down to the first element, taking 
steps. The time for this
loop can be no worse, so this is the worst case that we wish to analyze here.
For this worst case:
This recurrence may be solved using the iteration method; this solution
is given on Page 156 of the textbook: 
.
and 
, so the 
algorithm is still faster. But when n=15, 
and
; so n=15 is the smallest value for which the
algorithm is faster.
on an array of size n, and
divides it into two pieces, of size q and n-q; recursive calls on
these take time 
and 
. Since each of the two
pieces has size at least 1, 
. The best-case
running time can be no better than that obtained by choosing q to
minimize the total time taken by the recursive calls. So, letting
denote the best-case running time for QUICKSORT:
Using the substitution method to solve this recurrence, we want to show that
for some constant c. For n=1 this is simply
, which is trivially true, establishing the base case. Now
we substitute this into the recurrence:
We need to minimize the expression 
over this
range of q. Taking the first derivative with respect to q yields:
This expression is equal to 0 when q=n-q (that is, 
), and is
not equal to 0 anywhere else in this range. To see
that this point is a minimum (as opposed to a maximum or a saddle point),
note that the derivative 
is positive for q>n-q (that is,
), so the function increases as q increases from
; and, the derivative is negative for 
, so
the function also increases as q decreases from 
.
This shows that 
is the minimum, so we have:
We can choose c small enough so that cn is dominated by 
,
giving:
Thus, the best-case running time of QUICKSORT is 
.
Now, assuming that STOOGE-SORT correctly sorts arrays of size <n (this is the induction hypothesis), show that it correctly sorts arrays of size n (for n>2).
Let 
denote A after line 2 is executed.
Line 2 may exchange two elements of the input, but in any case
contains a permutation of the input - so if we correctly sort this part of
then
we have correctly sorted the input. Since n>2, line 3's check fails and
the function does not terminate at line 4.
Define k according to line 5. We now want to show that lines 6-8
produce a properly sorted permutation. Consider the k+1
largest-valued elements in A (if this set is not uniquely defined
due to duplicate elements, the following argument will still apply to
some set of k+1 largest-valued elements). Before line 6, some
of these largest-valued elements
are among 
, and the remaining
largest-valued elements are among 
. After line 6,
is sorted correctly by the induction hypothesis, so these
remaining largest-valued elements must be among 
(since
there are at most k+1 such remaining largest-valued elements, and
has at least k+1 elements). Thus, all of the k+1
largest elements are among 
after line 6. Line 7
then correctly sorts 
(by the induction hypothesis),
so the k+1 largest elements are among 
and are in
correct sorted order at that point.
The remaining smaller elements are properly
placed in 
, and after line 8 is executed, these are
correctly sorted as well. At this point, the entire array is
correctly sorted.
Thus, arrays of size n are also correctly sorted. By induction, STOOGE-SORT correctly sorts arrays of all sizes.
(b) Say STOOGE-SORT requires 
time to sort an array of size n.
During a call to STOOGE-SORT, lines 1-5 take only 
time.
Each recursive call in lines 6-8 is done on an array of size
. So, we have the recurrence:
We can apply the master theorem (page 62) with a=3 and 
.
Since 
is 
, it is 
,
since this is about 
if we pick 
(other values of
would also work, as long as they aren't too large). So, case 1
of the master theorem applies, giving:
So, it is even slower than insertion sort's worst case.
. So, modify
the PARTITION function used by QUICKSORT to first call SELECT to find the
median of the array (in 
time), then partition around this element
(in 
time).
The total time required by this modified PARTITION is not (asymptotically)
worse; it is still 
. But this modified PARTITION will always
give balanced partitions of 
elements each (rounded up or down).
As shown on page 157, this gives a running time for QUICKSORT that is
; this is now a worst-case running time since the use of SELECT
guarantees that it is always achieved.
One additional
detail: if there are duplicates of the median, there is no guarantee
that the partition will be exactly balanced as described above. There are
a variety of ways to handle this. One simple hack is to (temporarily) add
small, differing amounts to each duplicate of the median - small enough so
that none of their values becomes larger than the next larger value in the
original array (so that the overall sorted order is not disrupted). Choose
these small, differing values in increasing order, so that we know what
their median is. This all takes only linear time, so the 
time for
PARTITION is unaffected.
We now know the unique median of the modified array, so
we get our completely balanced partition around this,
and then change the temporarily modified values
back to their original value (the original duplicated median value).
. Given a desired target weight t with
, WEIGHTED-SELECT
finds an element 
satisfying 
and
. So calling WEIGHTED-SELECT with
would give the weighted median.
Note that WEIGHTED-SELECT simply calls SELECT on line 3
to find a good element (the median) about
which to partition. Since we already know that SELECT takes 
time in
the worst-case, there is no need to use the clever recursive method from
inside SELECT for this purpose.
Note that the MODIFIED-PARTITION function called on line 4 partitions around x, as described in step 4 on Page 190; it also carries the weights around with the elements, so W must be passed in. Also note that the arguments to SELECT are specified in the same order as they were for RANDOMIZED-SELECT on Page 187.
The remainder of the function is similar to SELECT, except that it uses
weight rather than
number of elements to decide which partition to recurse into.
Lines 5-7 count up the total weight 
on the low side of the partition.
If t is larger than this total weight, then we must be looking for an
element on the high side of the partition, so we recurse there (appropriately
reducing our target weight since we are removing the elements on the low
side of the partition from future consideration). Otherwise, the element
we seek is on the low side of the partition, so we recurse there.
WEIGHTED-SELECT(X,W,p,r,t)1 if p=r
2 then return
3
SELECT(X,p,r,
)
4
MODIFIED-PARTITION(X,W,p,r,x)
5
6 for
to q
7 do
8 if
9 then return WEIGHTED-SELECT(X,W,p,q,t)
10 else return WEIGHTED-SELECT(X,W,q+1,r,
)
We now analyze the time 
required to compute the weighted median
of n elements.
Lines 1-2, 5, and 8 take constant (
) time, line 3 takes 
time
(page 191), line 4 takes 
time (page 155; passing in the element
about which to partition does not change this running time),
and lines 5-7 loop
through at most n elements doing constant work with each for a
total 
time. The total for lines 1-8 is thus 
. Since
we partition around element number 
(and we
obtain exactly this specified partition, since all elements are distinct as
given in the problem), lines 8-9 recurse on 
or
elements.
To get an upper bound on running time, we now have the recurrence:
Use the substitution method to show that 
. Pick c
large enough so this is true for n=1. Now substitute into the recurrence:
Pick c large enough so that 
dominates 
, giving:
The lower bound is very similar. We have:
Use the substitution method to show that 
. Pick c
small enough so this is true for all 
(
is a constant
defined below).
Now substitute into the recurrence:
We can pick c small enough so that 
is dominated by
for 
, by picking 
sufficiently large
(this serves to define 
). So:
Combining these, 
.