Write solveRecurrence(a, b, d) that applies the master theorem to T(n) = a * T(n / b) + O(n^d), with a >= 1, b >= 2 and d >= 0, and returns the answer as a string in exactly this format:
- combine step dominates (
d > log_b(a)): "O(n^d)" - balanced (
d = log_b(a)): "O(n^d log n)" - recursion dominates (
d < log_b(a)): "O(n^e)" with e = log_b(a)
Write the exponent as a number rounded to 3 decimals, with trailing zeros dropped (2, 1.585). Two special spellings: an exponent of 1 is written n (so "O(n)" and "O(n log n)"), and an exponent of 0 with the log factor is written "O(log n)".
Beware of floating-point: Math.log(1000) / Math.log(10) is not exactly 3 in JavaScript.