Мастер теоремы для подзадач различных размеров

Question

родовых образуют Master theorem «ы упоминает, что:

предполагается, что все подзадачи, по существу, тот же размер

Akra–Bazzi method применяется, когда:

Субъекты имеют существенно разные размеры

Но каковы критерии для по существу разные? Например, у меня есть рекуррентное соотношение, как:

T(n) = T(n/4) + T(3n/4) + cn 
(c is some constant) 

Могу ли я использовать теорему мастер, чтобы решить эту связь (например, аппроксимирующей ее как T(n) = 2T(3n/4) + cn)? Или, другими словами, эти размеры подзадачи «по существу одинаковы» или они уже «существенно отличаются»?

Answer 1

Предполагая c некоторая константа, то есть: T(n) = T(n/4) + T(3n/4) + O(n)

Решая это с помощью метода Акра-Bazzi дает O(n^2)

Решая его, предположив T(n) = 2T(3n/4) + O(n) дает O(n^2.4094) (ехр округляется до 4 дп.)

Итак, просто попробовав, вы можете подтвердить, что они уже существенно отличаются.