Пусть:
А – алгоритм решения некоторого класса задач и n-размерность одной задачи из этого клааса (в частном случае n может быть, например длинной последовательности в рассмотренном выше алгоитме, количеством слов в анализируемом тексте и т.п.);
функция fA(n) даст верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм А для решения любой задачи размерности n.
Тогда алгоритм называется полиномиальным, если fA(n) растет не быстрее чем полином от n. В противном случае алгоритм А называется экспоненциальным. Так, функции типа kn, kn2,kn3,..., где k – коэфициент, могут рассматриваться как полиномиальные, а функции типа 2n, nn, n!... как экспоненциальнные.

Для достаточно больших n значение экспоненциальной функции всегда превышает значение полиномиальной функции. Для малых n это не всегда справедливо, но всегда есть такое n, для которого значение экспоненциальной функции превышает аналогичное для полиномиальной.

Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)]. Применительно к решению задачи на ЭВМ это время является в большинстве случаев свойством самого алгоритма и слабо зависит от машины, на которой решается соотвтствующая алгоритму программа.

Кроме временной сложности алгортмов существуют и другие меры сложности. Так, сложность можно характиризовать числом операций N (применительно к конкретной ЭВМ) и общим объемом информации Р, т.е общим количеством слов, используемых при выполнении алгоритма. Тогда время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значения Т и Р называют соответственно вычислительной и емкостной сложностью алгоритма.