Время выполнения алгоритма, которое приблизительно соответствует функции длины входа. Например, если время выполнения алгоритма описывается функцией O(2n), где n - количество битов входа, то при увеличении длины входа на один бит (n+1) время выполнения алгоритма удвоится