Problem : 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.