Как доказать, какая из следующих функций обладает большей скоростью роста?

Question

Я сталкивался с этим вопросом.Чтобы доказать, было ли следующее утверждение истинным или ложным
Пусть f (n) = n + log n, затем f (n) = O (log ^ 2 n).

Я не уверен относительнокак я могу доказать или опровергнуть, является ли log ^ 2n верхней границей для n или нет.Может ли кто-нибудь помочь мне построить доказательство для того же.

Answer 1

Рассмотрим функцию

g(x) = x(ln x)^2      ; x > 0

Эта функция является положительной и увеличивается для 0 < x < e^(-2).

Чтобы понять, почему это так, давайте вычислим ее производную:

g'(x) = 1*(ln x)^2 + x*2(ln x)/x

в основном потому, что производная ln x равна 1/x.Тогда

g'(x) = (ln x)((ln x) + 2)

, что положительно для 0 < x < e^(-2), поскольку оба фактора в этом интервале отрицательны.

Это доказывает, что g(x) положительно и увеличивается в интервале (0, e^(-2)).Следовательно, существует положительная константа c такая, что

g(x) > c      ; if x is small enough

, что означает, что

g(1/n) > c    ; if n is large enough

или

(1/n)(ln n)^2 > c

или

n < (1/c)(ln n)^2 = O((ln n)^2)

и поскольку ln n также O((ln n)^2), мы получаем

n + (ln n) = O((ln n)^2)

, как мы хотели видеть.