为期末考试做准备:渐近记法

Question

我现在正在为我的算法期末考试做准备。这不是一道家庭作业题，而是一道古老的期末考试题。

Show that f(n) = 4logn + log log n is big theta of logn. 

显然，log比log小得多，因此无关紧要。但是我怎么才能正式地展示它呢？我对limits和L‘’hopital很熟悉，所以如果你能告诉我如何使用这种方法，我将不胜感激。

Answer 1

记住big theta的定义。如果满足以下条件，则函数f(x)在Theta(g(x))中

​

你有f(x) = 4*log(x) + log(log(x))和g(x) = log(x)。现在，我们必须证明c_0、c_1和x_0存在满足条件的值。

如果我们让c_0 = 1和x_0足够大到log(log(x_0)) > 0 (确切的数字取决于您的对数的底数，但是总是有这样的数字，我们实际上不需要知道它)，那么很容易证明第一个不等式对于所有x > x_0：log(x) <= 4*log(x) + log(log(x))都是正确的(提示：log(log(x))已经是> 0，对数函数是单调递增的。

现在让我们选择c_1 = 5。第二个不等式现在变成了4*log(x) + log(log(x)) <= 5*log(x)，它简化为

log(log(x)) <= log(x)

适用于所有x > x_0。我会把这个证明留给你作为练习。:-)

Answer 2

查找c1、c2和no.的简单方法

查找上限:

 f(n) = 4logn+loglogn


    For all sufficience value of n>=2

        4logn <= 4 logn   
        loglogn <= logn 

    Thus , 

     f(n) = 4logn+loglogn <= 4logn+logn
                          <= 5logn
                           = O(logn)       // where c1 can be 5 and n0 =2

查找下限:

   f(n) = 4logn+loglogn

   For all sufficience value of n>=2

      f(n) = 4logn+loglogn >= logn
    Thus,              f(n) =  Ω(logn)   // where c2 can be 1 and n0=2


  so , 
                        f(n) = Ɵ(logn)