экспоненциальная зависимость

Ответ от Булат 1[гуру]
В дополнение к ответу Магистра Брома.
Экспоненциальная зависимость (вместе с полиномиальной) - очень важная вещь в математике вообще, алгебре, анализе и теории информации в частности.
Например, в анализе и теории информации есть очень важное понятие - "функция ограничена относительно другой функции". Что это значит? Вот, например, возьмём функцию вида f(x) = k*x и g(x) = m*x^2. Начнём x увеличивать. Казалось бы, всегда можно подобрать параметр k довольно большим и параметр m довольно маленьким, так, что всегда f будет больше g, например, f = 100000*x, g = 0,00001 * x^2. Однако оказывается, что это не так, и как ни выбирай k и m, найдётся такой x, после которого g начнёт превышать f и будет больше неё уже всегда. Это и означает, что любая функция вида k*x ограничена относительно любой функции вида m*x^2 (если только m не равно 0). Это позволяет нам сравнивать функции такого-то ВИДА, не конкретизируя наши параметры k, m и т. д.
Так вот, есть так называемый класс полиномиальных функций - это функции ВИДА f(x) = a + b*x + c*x^2 + d*x^3 + .и т. д. (число слагаемых должно быть конечным). Попросту говоря, многочлены.
Так вот, оказывается, ВСЕ полиномиальные функции ограничены относительно ЛЮБОЙ экспоненциальной! (показатель степени любой, не обязательно e, лишь бы был больше 1).
Т. е. если взять функцию f(x) = 1000000 + 100000*x + 1000000*x^2+100000*x^3, и сравнить с функцией g(x) = 1,00001 ^ x, то всё равно найдётся какой-то пусть и гигантский x, после которого g > f.
Это очень важно для создания алгоритмов программ, т. к. если мы знаем, что наша программа выполняется за экспоненциальное время (пусть даже с параметром очень маленьким, типа 1,0001^x), то на каком-то довольно большом объёме данных она по-любому будет работать медленнее, чем алгоритм Васи, который полиномиальный, пусть даже с большими параметрами.