Short Answer (2 points each) Answer the following questions using the simplest possible notation unless otherwise stated. Assume in recurrences that f(n) is (1) for constant values of n.

(a) Solution to the following recurrence T(n) = 3T(n/3) + n

(b) Solution to the following recurrence T(n) = 4T(n/2) + n

c) Solution to the following recurrence relation: f(n) = 3f(n 1) 2f(n 2) + 2^n . For this problem, give your answer in big-O notation.

d) Solution to the following recurrence relation: T(n) = 8T( n)+log^2 n

e) Worst-case runtime of randomized QuickSort on a list with n elements?

f) Expected time to do a search in a skip list containing n items?

g) Consider a certain operation OP. Say that over n calls to OP, the i-th call takes (i) time. What is the amortized cost of OP?

h) You flip n fair coins, and add each coin, one after the other, to the end of a row after flipping. Call a coin satisfied if it has the same value as its right neighbor in the row (the last coin in the row is never satisfied). What is the expected number of satisfied coins? For this problem, Give an exact answer (i.e. not just within )