Оценить скорость роста последовательности

[_mv]

Здравствуйте, уважаемые посетители форума!
Пожалуйста, подскажите, как решаются подобные задачи - у меня не было дискретных структур:

"Про последовательность $T(n)$ известно, что $T(n)=3T( \lceil n/3 \rceil ) + n$. Оцените скорость роста $T(n)$".

Спасибо.

[Хорхе]

$T(3^n)=?$

[_mv]

Супер! Спасибо, она растет экспоненциально!
Но меня вот смущает слагаемое $3^{n}$
Ведь это не константа...
В $T(3^n)=3T(3^{n-1})+3^n$

Что можно почитать на эту тему?
Еще раз спасибо.

[Хорхе]

Ну где ж экспоненциально?

И, кстати, Вы $T(3^n)$ мне пока не выписали.

[_mv]

Как не выписал?
А вот же:

_mv в сообщении #568358 писал(а):

$T(3^n)=3T(3^{n-1})+3^n$

[ewert]

_mv в сообщении #568358 писал(а):

В $T(3^n)=3T(3^{n-1})+3^n$

Если $a_n=a_{n-1}+3^n$, то $a_n=C\cdot3^n+A\cdot n\cdot3^n$, где $C$ -- произвольная постоянная и $A$ определяется подстановкой в уравнение.

[_mv]

ewert
Это да, а как называется такая скорость роста?

[ewert]

Никак не называется. Только это, между прочим, ещё не она.

[_mv]

ewert
Да. Скорость роста - $O(n \lg n)$
Основная теорема о рекуррентных соотношениях.