如何证明θ(Log)=o(Log)？

Question

我正在解决一个来自CLRS的问题，我们需要证明(ceil(lg ))！是多项式有界的。

Let g(n)=(ceil(lg lg n))!

lg(g(n))=lg((ceil(lg lg n))!)
        =theta(ceil(lg lg n) * lg (ceil(lg lg n))) [since lg(n!)=theta(n * lg n)
                                                    and replacing n by ceil(lg lg n) here.]
        =theta((lg lg n) * (lg lg lg n))  ----(1)  [since ceil(n)=theta(n)
                                                    and replacing n by (lg lg n) here.]

，如果我能证明θ(lg，n)=o(n)

=>theta(lg lg lg n)=o(lg lg n)
=>theta((lg lg n) * (lg lg lg n))=o((lg lg n) * (lg lg n))
                                 =o((lg lg n)^2)
                                 =o(lg^2(lg n))
                                 =o(lg n)  ----(2) [Polylogarithmic functions grow slower than 
                                                    polynomial functions.
                                                    =>log^b(n)=o(n^a)
                                                    =>log^2(log n)=o(logn^1)
                                                    =>log^2(log n)=o(log n)]

From (1) and (2) we have log(g(n))=o(log n)
=>g(n)=o(n^a) that is g(n) is polynomially bounded.

我面临的唯一问题是证明θ(Lg n)=o(n)。请帮帮我！

Answer 1

要证明(ceil(lg lg n))!是多项式有界的，也可以使用斯特林近似。

斯特林说，n!主要是近似的，类似于n^n。因此，以下情况成立：

ceil(lg lg n)! < (1 + lg lg n)! 
               < (1 + lg lg n)^(1 + lg lg n) 
               = (1 + lg lg n) * (1 + lg lg n)^(lg lg n)
               < (1 + lg lg n) * (2 * lg lg n)^(lg lg n)
               < (1 + lg lg n) * (lg n) * (lg lg n)^(lg lg n)

现在只需要证明(lg lg n) ^ (lg lg n)是多项式有界的：

             (lg lg n)^(lg lg n) < n
<=>   lg ( (lg lg n)^(lg lg n) ) < lg n
 =>   lg ( (lg lg n)^(lg lg n) ) = (lg lg n) * (lg lg lg n) 
                                 < sqrt(lg n) * sqrt(lg n)
                                 = lg n

总之，你得到的

ceil(lg lg n)! < (1 + lg lg n) * (lg n) * n

不用地标符号。

对于您的问题(证明theta(lg n)=o(n))：f in o(g)表示lim f(n)/g(n) -> 0表示n ->无穷大。由于lim (lg n)/n -> 0，lg n在o(n)。e in Theta(f)的意思是0 < liminf e(n)/f(n) <= limsup e(n)/f(n) < infinity。

因此，e在Theta(f)中有一个由c* f(n)表示的上界，对于一个恒数c。

所以e在Theta(lg n)中是以c * lg n为界的，由于lim c lg n / n -> 0，e也在o(n)中。