反因子的增长

Question

考虑反因子函数,f(n)= k其中k!是最大的因子<= n.我被告知逆因子函数是O(log n/log log n).这是真的吗？或者它只是渐近增长的非常好的近似值？我尝试了所有的方法给的东西非常接近的log(n)/日志的log(n)(一个小的因素或分母小项),但并不完全.

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).