Является ли функция этажа (log n)! O(n), Ω(n) или Θ(n)?

Question

Я очень смущен тем, как я могу оценить пол (журнал n)!

Answer 1

Вы можете игнорировать floor; поскольку x-1 < floor(x) <= x для всех x, вы можете легко показать, что если g(x) = floor(f(x)), затем g = Θ(f),

Используя приближение Стирлинга, вы можете сказать, что (log n)! является Θ((log n)^(log n)), что упрощает Θ(n^(log log n)) что явно Ω(n),

(спасибо Марку Дикинсону за исправление моей ужасной математики; см. здесь для доказательства).