Show that log(n^3) is O(log(n)), then show that log(n^2+10) is also O(log(n)).
Favorites|Homepage
Subscriptions | sitemap
HOME > Mathematics > Show that log(n^3) is O(log(n)), then show that log(n^2+10) is also O(log(n)).

Show that log(n^3) is O(log(n)), then show that log(n^2+10) is also O(log(n)).

[From: ] [author: ] [Date: 11-10-14] [Hit: ]
Now, log(n^3) is O(log(n)), because lim (n---> infinity) log (n^3) / log(n) = lim 3*log(n) /log(n) = 3. Likewise, we can prove that lim (n---> infinity) log(n^2 + 10)/log(n)is a finite number........
I am stuck on this problem for my class. Any help is greatly appreciated.

-
Fact:
IF lim( as x---> a) |f(x) / g(x)| exists and is a finite number, THEN f(x) = O (g(x)), as x ---> a.

Now, log(n^3) is O(log(n)), because lim (n---> infinity) log (n^3) / log(n) = lim 3*log(n) /log(n) = 3. Likewise, we can prove that lim (n---> infinity) log(n^2 + 10)/log(n) is a finite number... more specifically, it is equal to two.

To see that, we can use the squeezing principle: Obviously log(n^2)/log(n) < log(n^2 + 10)/log(n) < log (n^2 + n^2) / log(n), for large values of n... (***)

Now let n ---> infinity. Clearly, the left hand side of (***) will converge to a limit of 2, and the right hand side log (n^2 + n^2) / log(n) = log (2*n^2) / log(n) = (log 2 + 2log(n)) / log(n) ----> 0 + 2 = 2. This forces that the middle term (i.e. the term of our interest) also converges, and it converges to 2.

More generally, log(n^2+10) is also O(log(n)).

I hope that helps. Thanks,

-
log(n^3) = 3*log(n)

f(n) = O(g(n)) iff exists constants c > 0 and n_0 > 0 with f(n) <= cg(n) for all n > n_0.

we can just let c = 3, and n_0 doesn't matter because both sides are the same.

for the second, you can note that n^2+10 < n^3 for well-chosen n_0, and logarithm is monotonically increasing function so x < y implies log(x) < log(y).
1
keywords: Show,log,that,is,also,10,show,then,Show that log(n^3) is O(log(n)), then show that log(n^2+10) is also O(log(n)).
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .