Рост обратного факториала

Question

Рассмотрим обратную факториальную функцию, f (n) = k, где k! является наибольшим факториалом <= n. Мне сказали, что обратная факториальная функция - O (log n / log log n). Это правда? Или это действительно очень хорошее приближение к асимптотическому росту? Все методы, которые я попробовал, дают вещи, очень близкие к log (n) / log log (n) (либо малый множитель, либо маленький член в знаменателе), но не совсем. </p>

Answer 1

Помните, что когда мы используем O (...), постоянные факторы не имеют значения, и любой термин, который растет медленнее, чем другой термин, можно отбросить. ~ означает «пропорционален».

Если k большое, то n = k! ~ k^k. Так что log n ~ k log k или k ~ log n / log k или k ~ log n / log(log n / log k) = log n / (log log n - log log k). Потому что n >> k мы можем отбросить термин в знаменателе, и мы получим k ~ log n / log log n, поэтому k = O(log n / log log n).

Answer 2

Начните с Приближение Стирлинга для ln (k!) И работайте в обратном направлении.Извиняюсь за то, что не все уладил;кажется, мой мозг не работает сегодня вечером.