Mini #1, 15451 Fall 2013 ======================== This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 3. Please use the subject line "15-451 MINI #1" in your email. Problem 1: For each pair of functions below, list which of the following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) = o(f(n)). (a) f(n) = n*ln(n), g(n) = n*lg(n). ["ln" is base-e, "lg" is base-2] (b) f(n) = n^2 / log(n), g(n) = n^{lg(3)}. ["^" is "to the power"] (c) f(n) = 2^n, g(n) = 2^{2n}. (You do not have to prove your answers.) Problem 2. In class, we discussed a deterministic linear-time algorithm for finding the median (or kth smallest element) of an unsorted array. Our analysis of this algorithm gave the recurrence: T(n) <= T(n/5) + T(7n/10) + cn. Suppose we changed the algorithm so that rather than breaking up the array into groups of size 5, we used groups of size 7 instead. (a) Write down the recurrence that results from this change of 5 to 7. (Explain your reasoning) (b) What does this recurrence solve to?