Можно показать, что нижняя граница

3n² –100n+6  (n³) при С=1.

Неравенство 3n² –100n+6  n³ не выполняется.

3n² –100n+6=(n)

C₁= , n>n₀.

C ₁n 3n²-100n+6 (верхняя граница)

C₁n  3n²-100n+6 (нижняя граница)

Учитывая сложность оценки , считают, что предпочтительнее являются алгоритмы, имеющие меньший порядок роста. Т. е. если одну и ту же задачу можно решить двумя алгоритмами, для которых порядок сложности кратен O(N²) и O(N³) соответственно, то более эффективным при  будет первый алгоритм.

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

Например:

f₁(N)=100n²

f₂(N)=5n³

n₀=20 – критическая точка.

Другой причиной предпочтения алгоритмов с меньшим порядком сложности является то, что чем меньше порядок сложности, тем больший размер задачи N можно решить практически.

Вывод: следует создавать алгоритмы, для которых порядок сложности кратен N или logN : O(N), O(logN), O(MlogN).

Алгоритмы, порядок сложности которых кратен O(2ⁿ), O(aⁿ) дают экспоненциальный рост сложности.

Таблица скорости роста сложности для различных алгоритмов.

N	ln(N)	N	n*lg(N)	n2	2n	n!
10	3 нс	10 нс	33 нс	100 нс	1 мкс	3,63 мс
20	4 нс	20 нс	86 нс	400 нс	1 мс	77 лет
50				2,5 мкс	13 дней
100					4*1013 лет
105			0,13 мс	100 мс
106				10 с
107				16,7 мин
109	30 мс	1 с	29,9 с	31,7 лет

Пример 6:

Нужно учитывать, что больший порядок роста сложности алгоритмов как правило имеет меньшую константу С₁ по сравнению с малым порядком роста сложности, характеризующимся константой С₂.

В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n0).

Пусть заданы пять алгоритмов решения одной и той же задачи, имеющие следующие сложности роста сложности:

А1: 100N

А2: 100N*logN

А3: 10N²

А4: N³

А5: 2^N

Тогда для задач с N=29 более быстродействующим будет А5 (f(N) ~ 4512). Другие алгоритмы при подстановке дадут существенно более низкие показатели.

При N=1058 предпочтительным оказывается А3.

При N=591024 самым эффективным будет А2.

При N>1024 предпочтителен А1.

Для программ, состоящих из нескольких последовательно или параллельно выполняющихся алгоритмов, сложность оценивается по правилу сумм и правилу произведений.

Правило сумм: Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O(f(n)) и O(g(n)) соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов:

T(n) = T₁(n)+T₂(n)

В общем случае получаем:

T(n)  O(max f(n), g(n))

Правило произведений: Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O(f(n)) и O(g(n)) соответственно, определяется как произведение временных сложностей каждого из алгоритмов:

T(n) = T₁(n)*T₂(n)

В общем случае:

T(n)  O( f(n)*g(n))