Решение рекуррентности T (n) = T (n / 3) + O (logn) + n путем точной оценки

Question

Можно ли отбрасывать нижние члены при решении повторений, как в этом случае я решил отбросить O (logn).

прошу прощения за плохую почерк!Вот моя попытка решить рецидив:

Answer 1

Вы можете переписать O(log n) + n = Theta(n) и продолжить свой веселый путь с Главной теоремой, чтобы получить границу Theta(n).

Если вы хотите получить еще лучшую оценку, вы можете потрудиться проверитьT(n) = 3n/2 + c log^2 n для некоторой фиксированной константы c с использованием метода подстановки.