私は現在、アルゴリズムの最終段階に向けて勉強しています。これは宿題の問題ではなく、過去の期末試験に由来します。
Show that f(n) = 4logn + log log n is big theta of logn.
log log n が log n よりもかなり小さいため、重要でないことは明らかです。しかし、どうすればそれを正式に示すことができますか?私は制限とロピタルに精通しているので、その方法でそれを行う方法を教えていただければ幸いです。
私は現在、アルゴリズムの最終段階に向けて勉強しています。これは宿題の問題ではなく、過去の期末試験に由来します。
Show that f(n) = 4logn + log log n is big theta of logn.
log log n が log n よりもかなり小さいため、重要でないことは明らかです。しかし、どうすればそれを正式に示すことができますか?私は制限とロピタルに精通しているので、その方法でそれを行う方法を教えていただければ幸いです。
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)