Будь-яка задача може бути розв’язана за скінченну кількість кроків

Якщо ефективність алгоритму визначається обчислювальною складністю обробки многочлена порядку к, часто задовольняються оцінкою О(nk), не звертаючи уваги, на старший коефіцієнт і решту членів полінома

Існує алгоритмічна задача, яку можна розв’язати за скінченну кількість кроків

Існує алгоритмічна задача, яку можна розв’язати, та для якої справедливо наступне: для будь-якого алгоритму, що розв’язує цю задачу і що має складність в найгіршому випадку , можна знайти інший алгоритм із складністю такий, що майже для всіх виконується

Використання О-оцінювання дозволяє нам позбавити себе від врахування конкретного обчислювального пристрою для аналізу складності