Question

Weird recursion tree analysis. Suppose we have an algorithm that on problems of size n, recursively solves two problems of size n/2, with a “local running time” bounded by t(n) for some function t(n). That is, the algorithm’s total running time T(n) satisfies the recurrence relation T(n) ≤ 2T(n/2) + t(n). For simplicity, assume that n is a power of 2.

Prove the following using a recursion tree analysis

(a) If t(n) = O(n log n), then T(n) = O(n(log n)²).

(b) If t(n) = O(n/log n), then T(n) = O(n log log n).

(c) If t(n) = O(n/(log n)²), then T(n) = O(n).

Note that the Master Theorem itself cannot be used here, because the functions t(n) above are not of the form required by the Master Theorem.

Hint: for each level j, estimate the number of subproblems at that level, and the local running time for each subproblem at that level.

Answer 1