algorithm - 为我的期末学习：渐近符号

Question

我目前正在学习算法的期末考试。这不是家庭作业问题，而是来自旧的期末考试。

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

很明显，log log n 比 log n 小很多，因此微不足道。但是我怎样才能正式地展示它呢？我熟悉限制和 L'hopital，所以如果您能告诉我如何使用这种方法，我将不胜感激。

Answer 1

记住大θ的定义。一个函数f(x)在Theta(g(x))if

你有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)