Mini #1, 15451 Fall 2012 ======================== This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 4. Please use the subject line "15-451 MINI #1" in your email. Problem 0: Sign into the piazza discussion board system, using your andrew ID (so your TA can check off that you did it). Problem 1: Suppose f(n) = O(g(n)) and g(n) = O(h(n)). Does that imply that f(n) = O(h(n))? Explain why or give a counterexample. Problem 2: 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}. Problem 3: Consider the following algorithm for finding the largest element in an array A of size n: if (n==1) then return A[0]. else: - recursively, find the maximum value v1 in the left half of A - recursively, find the maximum value v2 in the right half of A - compare v1 with v2 and output the one that is larger. (a) Write a recurrence that describes the number of comparisons made by this algorithm on an input of size n (assume n is a power of 2). (b) Solve your recurrence from (a). Hint: try it for n = 1,2,4,8 and guess an *exact* formula for T(n). Then prove this is correct by induction. [Note: T(1)=0 since if n=1 the algorithm doesn't make any comparisons]