Рекуррентное отношение

Question

Я обычно решаю рекуррентные отношения, используя мастер-метод. Если он не работает, я пытаюсь использовать метод подстановки или метод рекурсивного дерева. Последние подходы занимают больше времени. Недавно я столкнулся с некоторым рекурсивным отношением, которое я не могу решить, используя нормальный метод. Я не хочу строгого ответа (если возможно, то это еще лучше). Я просто хочу знать, есть ли какой-либо метод, который получит границы для этих рекурсивных уравнений.

1) Т (п) = Т (п/10) + T (9 * п/10) +1

2) Т (п) = Т (п^1/2) + T (nn^1/2) + c * n

Answer 1

Для 1) основная теорема имеет обобщение для суммы T(α.n) в правой части. См. https://fr.wikipedia.org/wiki/Master_theorem#Extension (на французском языке).

В качестве неоднородного термина 1 вы можете попробовать линейное решение, a.n + b. Затем

a.n + b = a.n/10 + b + a.9n/10 + b + 1 

, который работает для любого a и b=-1.

Для 2), у меня нет подсказки, аргумент n - √n делает это довольно сложно. Линейная форма не работает.