Примеры. 1.«Пропылесосить ковер» требует время, линейно зависящее от его площади , то есть на ковер, площадь которого больше в два раза1.«Пропылесосить ковер» требует время, линейно зависящее от его площади 2.«Найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей
] данные – множество чисел, которые в некоторых системах счисления имеют длину ≤ n Тогда сложность алгоритма оценивается некоторой функцией ] даны два алгоритма с
в таком виде обычно получают оценки сложности алгоритмов.
|
, то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
, так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за 
раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за 
заходов.
, т.е. зависящей от n.
– функции сложности
, т.е. 
