Нужна помощь в решении проблемы несбалансированного дерева рекурсии

Question

Я пытаюсь решить проблему несбалансированного дерева рекурсии. Вот вопрос:

T (n) = T (n / 3) + T (2n / 5) + n ^ 3

Я пытался нарисовать дерево, но застрял на решение проблемы. Может кто-нибудь мне помочь? Спасибо.

Answer 1

Мы знаем, что порядок этой рекурсии не менее n ^ 3, потому что для любого шага используется n ^ 3. А также мы знаем, что T (n) <= 2T (2n / 5) + n ^ 3 и решение этой рекурсии по основной теореме равно o (n ^ 3). и, наконец, мы заключаем, что T (n) = theta (n ^ 3) </p>