Поведение временной сложности алгоритма в пределе, при увеличении размера задачи, называется асимптотической временной эффективностью.
Используются обозначения:
Θ – обозначение;
Ο– обозначение;
Ω– обозначение.
Θ – обозначение
Ο– обозначение
Ω– обозначение
Максимальный размер задачи
| Алгоритм | сложность | Максимальный размер задачи (единица времени 1 миллисекунда) | ||
| 1 сек | 1 мин | 1 час | ||
| А1 | n | 3.6*106 | ||
| А2 | n*log (n) | 2.0*105 | ||
| А3 | n 2 | |||
| А4 | n 3 | |||
| А5 | 2 n |
Влияние ускорения компьютеров в 10 раз
| Алгоритм | сложность | Максимальный размер задачи | |
| До ускорения | После ускорения | ||
| А1 | n | S1 | 10*S1 |
| А2 | n*log (n) | S2 | ≈10*S1 |
| А3 | n 2 | S3 | 3.16*S3 |
| А4 | n 3 | S4 | 2.15*S4 |
| А5 | 2 n | S5 | S5+3.3 |