A couple of problems came up during the problem session that I got
stuck on. Here are sketches of the answers:
(1) Problem 4-4(f)
Here, the guess is actually pretty easy if we think about a recursion tree.
At the top level is a single problem of size n.
At the next level are n^(1/2) problems of size n^(1/2).
At the next level are n^(3/4) problems of size n^(1/4).
At the next are n^(7/8) problems of size n^(1/8).
In general, at level i, there are n^((2^i-1)/2^i) problems of size
n^(1/2^i). Notice that the sum of the sizes of the problems on any
one level is n.
The contribution of the "+n" part of the recurrence is equal to the total of
the size of all the subproblems. Thus this will contribute n to the grand
total for each level. How many levels are there? We have to figure out
when n^(1/2^i) is equal to O(1). This happens when i is about log log n,
so there are loglog n levels of recursion, each contributing n to the grand
total. So we guess that T(n) is in Theta(n log log n).
Then you can do an inductive proof that this guess is correct.
The inductive step of the proof then works out very nicely, because if
T(k) = k log log k for k <= n, then
T(n+1) = sqrt(n+1)*sqrt(n+1)log log sqrt(n+1) + (n+1)
= (n+1)(log log (n+1) - 1) + (n+1)
= (n+1) log log (n+1)
(I'll leave the rest of the proof to you.)
------------------------
(2) Problem 10.3-8
The algorithm a student suggested during the problem session does work
(with a little modification).
For simplicity, let's assume distinct elements. (There's no loss of
generality in doing this, since if two elements are equal, we could
arbitrarily say that the leftmost one is smaller.)
Also, let's assume n is odd. (If n is even, we'll add a 0 to the left
end of X and an infinity to the right end of Y. This won't change the
median the two arrays, and it will make the number of elements in each
array odd.)
Let a and b be the medians of X and Y. (Since the two arrays are
sorted, these are trivial to find: just look at the elt in position
(n+1)/2) ).
Suppose a**a, the idea is symmetric: just interchange X and Y
in the description below).
Throw away the first half of X (those smaller than a) and the second
half of Y (those bigger than b), and find the median of the two
resulting arrays recursively.
Since there is one recursive call on a problem of size about half as
big, it's easy to see this will run in O(log n) time.
Why is this algorithm correct?
We want to show that the median of the two original arrays is
>= a and <= b (so that we're sure we're not throwing *it* away).
At most 2(n-1)/2 = n-1 elements are smaller than a (those elts
in the left half of each array). But exactly n-1 elements are smaller
than the median of all 2n elements. So the median of all elements is
at least a.
Similarly, at most 2(n-1)/2 = n-1 elements are larger than b (those
elts in the right half of each array). But exactly n elements are
larger than the median of the two arrays. So the median of the all
elements is < b.
Thus, the algorithm throws away (n-1)/2 elements larger than the
median and (n-1)/2 elements smaller than the median. So the median of
the resulting 2 arrays is also the median of the original two arrays.
Exercise: turn this into a formal proof of correctness.
**