Сравнение скорости роста функций. В чем ошибка?

Question

[PanchishinM]

Отметьте все верные утверждения. Пусть f,g,h:N→N.

Связался с этой темой и уже который раз не получается решить этот тест. Я подозреваю, что я что-то понимаю не правильно. Казалось бы элементарная тема, но уже, если честно, осточертело биться головой об стену.

Выше приведен тест с неверными вариантами ответа. Я бы хотел, чтобы компетентные люди ткнули носом в ошибки и разъяснили почему так, а не иначе.

Спасибо.

Answer 1

[Миша Кринкин]

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

Comments

[jcmvbkbc]

Хм, x^2 = O(x^3), но log(x^n) = n * log(x). Разве 2 * log(x) = O(3 * log(x))?

[Миша Кринкин]

@jcmvbkbc Разве 2 * log(x) = O(3 * log(x))? - ответ да, константный множитель не влияет в данном случае.