0

私は現在、アルゴリズムの最終段階に向けて勉強しています。これは宿題の問題ではなく、過去の期末試験に由来します。

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

log log n が log n よりもかなり小さいため、重要でないことは明らかです。しかし、どうすればそれを正式に示すことができますか?私は制限とロピタルに精通しているので、その方法でそれを行う方法を教えていただければ幸いです。

4

2 に答える 2

1

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)     
于 2013-04-12T13:26:56.773 に答える