Write Recurrences. For each triple a b d in the input, consider T(n) = a·T(n/b) + n^d with T(1) = 1.
- Print the Master-theorem verdict by comparing a with b^d:
a = b^d→ Θ(n^d log n);a < b^d→ Θ(n^d);a > b^d→ Θ(n^(log_b a)) (exponent with 2 decimals). - Evaluate T exactly with a recursive method for n = b⁰ … b¹⁰ and print the last three values with the ratio to the previous one.
For the input
2 2 1
the program prints
T(n) = 2 T(n/2) + n^1
Master theorem: a = b^d: Theta(n log n)
T(256) = 2304 (x2.25)
T(512) = 5120 (x2.22)
T(1024) = 11264 (x2.20)
Check that the measured ratio agrees with the verdict (for Θ(n log n) and b = 2 the ratio tends to slightly more than 2).