Problem 3: Suppose we are maintaining a data structure under a series of n operations. Let

f(k) denote the actual running time of the kth operation. For each of the following functions f,

determine the resulting amortized cost of a single operation.

a) f (k) = n2 if k is a power of 2, and f (k) = 1 otherwise.

b) f (k) = k if k is a Fibonacci number, and f (k) = 1 otherwise.

c) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) is

the number of ancestors of node k.