Сравнение функций асимптотически

Question

У меня есть 2 функции:

 f(n) = n*log(n)
 g(n) = n^(1.1) * log(log(log(n)))

Я хочу знать, как эти функции сравниваются друг с другом.Из того, что я понимаю, f (n) всегда будет расти быстрее, чем g (n).Другими словами: f (n) в ω (g (n))

Я предполагаю, что база 10 журналов, но это действительно не имеет значения, поскольку любая база может быть использована.Я попробовал несколько комбинаций n и c, так как, кажется, имеет место следующее соотношение:

 f(n) ≥ c g(n) ≥ 0

Одна комбинация, которая мне показалась, была следующей:

 c = 0
 n = 10^10

В этом случае:

f(10^10) = (10^10) log(10^10) = (10^10)*(10) = 10^11
c*g(n)   = 0 * (10^10)^(1.1) * log(log(log(10^10))
         = 0 * (10^11) * log(log(10))
         = 0 * (10^11) * log(1)
         = 0 * (10^11) * 0 = 0

Следовательно, f (n) всегда будет больше, чем g (n), и отношение будет f (n), это ω (n).

Правильно ли мое понимание здесь?

отредактировано: для исправления

Answer 1

Прежде всего, выпадающая вам комбинация не работает, потому что она недействительна.Функция f(x) называется O(g(x)) тогда и только тогда, когда существует действительное число x' и положительное действительное число c, такое что f(x)≤cg(x) для всех x≥x'.Вы используете c=0, что не является положительным, и поэтому использование его для понимания асимптотической сложности не поможет.

Но, что более важно, в вашем примере это не тот случай, когда f(x)=Ω(g(x)).На самом деле, это на самом деле f(x)=O(g(x)).Вы можете видеть это, потому что log(n)=O(n^0.1) ( доказательство здесь ), поэтому nlog(n)=O(n^1.1), так nlog(n)=O(n^1.1 log(log(log(n)))) и, таким образом, f(x)=O(g(x)).