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 aa, 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.