3. Сложность корня O (√n)
4. Сложность степени O (n^x)
Сложность многочленов увеличивается с ростом степени
А) n– Одиночный цикл от 1 до n даёт O(n)
Б) n^2 – сумма арифметической прогрессии
Простые программы можно анализировать с помощью подсчёта в них количества вложенных циклов. Одиночный цикл в n итераций даёт f( n ) = n. Цикл внутри цикла — f( n ) = n2. Цикл внутри цикла внутри цикла — f( n ) = n3. И так далее.
5. Экспоненты имеют большую сложность, чем полиномы, если коэффициенты положительные кратные n - O(2^n)
6. Факториалы имеют большую сложность, чем степень. Краткое доказательство состоит в том, что и факториалы, и степень имеют одинаковое количество умножений, но числа, которые умножаются, растут для факториалов, оставаясь неизменными для степени. O(n!)