Find a probabilistic variation of the program that has O(n log n) expected time complexity.
Hint: A proof by induction can be used to show that T(n) = O(n log n) if T(n) £ cn + 2/n å i=0n-1 T(i).
Hint: Note that a univariate polynomial s(x) of degree N has at most N roots, that is, N values x0 such that s(x0) = 0.
Hint: Use part (a) of the problem to check that the inputs have the form ai1bj1ai2bj2 · · · aimbjm with i2 - i1 - 1 = 0, i3 - i2 - 1 = 0, ¼ and j1 - j2 - 1 = 0, j2 - j3 - 1 = 0, ¼
Hint: Allow M2 to halt in a rejecting configuration with probability (1/2)n and to start a new simulation of M1 with probability 1 - (1/2)n, after simulating a nonaccepting computation of M1.