Доказательство индукции в алгоритмах

Question

Предположим, что произвольная r

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

show T(n) <= Dcn для некоторой константы D

, переработав доказательство индукции, используйте выражение, чтобы утверждать, что:

T(n) <= Dcn не выполняется для r=3.

Answer 1

Взгляните на теорему Акра-Бацци . Это обобщение основной теоремы , которая не требует подзадач одинакового размера.