Определить точное время выполнения алгоритма по этой нотации нельзя, дает понятие о масштабе сложности, а не о точном его значении.
O(1) - затраты времени не зависят от размера задачи
O(log(n)) - при увеличении размера задачи вдвое, затраты времени меняются на постоянную величину
O(n) - при увеличении размера задачи в 2 раза, затраты времени возрастут тоже в два раза
O(n^2) - при увеличении размера задачи в 2 раза, затраты времени возрастут примерно в четыре раза
O(n*log(n)) - при увеличении задачи в два раза, затраты времени возрастут в два раза, плюс некоторая прибавка, относительный вклад которой уменьшается с ростом n. При малых n может вносить очень большой вклад. O(n*log(n)) начинает расти как квадрат при малых n, но потом рост замедляется почти до линейного
O(n^p) - полиномиальный алгоритмы, остающиеся мечтой для некоторых задач.
O(a^n), O(n!), O(n^n) - неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени
Средний
Простой
