Помогите, пожалуйста, найти определение "скорости роста последовательности"

С определением встретился тут (друг поступал, а мне просто задачки понравились):
http://mit.spbau.ru/files/20100424_sobes_cs.pdf

Скажите только определение, а решить интересно самому.
Спасибо заранее.

Ну, точных определений Вы скорее всего не найдёте. Потому что "скорость роста" есть некий сленг, хотя и очевидный всем, кто имеет дело с пределами.

Если есть две растущие куда-нибудь последовательности a(n) и b(n), то про них говорят, что скорость их роста одинакова, если верхний предел их отношения не превосходит некоторой положительной постоянной, и нижний предел не меньше некоторой положительной постоянной. Т.е. отношение a(n)/b(n) отделено от нуля и ограничено сверху начиная с некоторого n.
Когда говорят про определение скорости роста последовательности, имеют в виду сравнение её с некоторой "канонической" растущей последовательностью, чья скорость роста всем понятна: например, со степенной, показательной или логарифмически растущей последовательностью. Так, последовательность (n+7)^5 растёт как n^5, (3+25/n^2)^n - как 3^n, и т.п. "Оценить скорость роста" рекуррентно заданной последовательности T(n) - значит, предъявить две такие явным образом заданные последовательности a(n) <= b(n), что верхний предел отношения T(n)/b(n) не больше единицы, а нижний предел отношения T(n)/a(n) не меньше единицы. Тогда можно будет сказать, что T(n) растёт не быстрее b(n), но не медленнее a(n). Лучше всего, если эти последовательности совпадут - тогда скорость роста (в данном случае её называют асимптотикой) T(n) найдена точно, или если a(n) и b(n) отличаются на константу.