Proving lg (n!) = O (n!)

Question

У меня возникли проблемы с хорошим способом доказать это по некоторым причинам. Я очень ржав в решении ограничений и математики в целом.

Прежде всего: у меня создается впечатление, что вы можете отделить лимиты от закона умножения. Так, в настоящее время я просто добраться до

Ит _{п → ∞} (ГПВ (п) ⋅n ^0,5) ⋅ Ит _{п → ∞} ((е/п) п )

такая же, как предел что-то раз предел 0. Таким образом, он должен быть равен 0.

это даже действует, или я должен вернуться назад и просто научиться извлекать г N ^0,5 ⋅lg (n) и другие подобные составные функции?

Очевидно, что эта проблема тривиальна, мне просто интересно, был ли я даже подход к действию.

Answer 1

Это легко доказать. Помните, что f(z) = O(z), если существуют M и z0, такие, что для всех z > z0: |f(z)| < M|z|.

Теперь, поскольку мы знаем, что |log(z)| < |z| для всех z > 1, мы просто можем заменить z = n!, и есть наше доказательство. Чтобы быть ясным, это сделают z0 = 1 и M = 1.

Если кто-то говорит, что это неправда, они, вероятно, забывают, что самая распространенная нотация Big Oh (Capital omicron) предлагает верхнюю границу, поэтому граница не обязательно должна быть жесткой.

Обновление: Записка о законе умножения для лимитов. Вы можете разбить только предел, если существуют оба ограничения . Например, если у вас есть предел n/n, когда n приближается к бесконечности, вы не можете отделить это до предела n раз предел 1/n, так как предел n не существует. Ваш первый лимит явно расходится, поэтому вы не можете использовать этот подход.