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,
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).
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).