Induction Proof in Algorithms

Question

Assume an arbitrary r

T(n) <= cn + T(n/r) + T (3n/4)

show T(n) <= Dcn for some constant D

by reworking the induction proof, use the expression to argue that:

T(n) <= Dcn does not hold for r=3.

Answer 1

Have a look at the Akra-Bazzi theorem. This is a generalization of the master theorem that does not require subproblems of equal size.