T(n) = c1T(n/a) + c2(T/b) + f(n)

问题:

Example T(n)=T(n/3)+T(n/4)+3n is this solvable with iterative master theorem or recursion tree.Can someone solve it analytically to show how it's done ?

回答1:

We can expand T(n) with a binomial summation:

(after some steps - can be proven by induction

For some depth of expansion / recursion k.

Where do we terminate? When the parameters to all instances of f(n) reach a certain threshold C. Thus the maximum depth of expansion:

We choose the smallest between a, b because the parameter with only powers of min(a, b) decreases at the slowest rate:

Thus the general expression for T(n) is:

The existence of a closed form analytical solution depends on the form of f(n). For the example provided:

The inner summation is the expansion of a binomial bracket raised to power j:

This is a geometric series, and equals (using standard formula):

Now since 7/12 is less than 1, the power term in the above result becomes vanishingly small for large values of k (and thus n). Therefore in the limit of large n:

Truth be told the above example could have been done more straightforwardly with a recursion tree; but the same does not go for e.g. other powers of n, e.g. f(n) = Cn^2, which can be trivially incorporated into the general formula.