Question: By changing the potential function, you can prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree and S(i) be the sum of the weights of all nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let N be the number of nodes in the tree and M be the number of accesses. Prove the following two theorems.
a. The total access time is O(M + (M + N) log N).
b. If qi is the total number of times that item i is accessed and qi > 0 for all i, then the total access time is O(M + log(M/qi )).