- #1

Miike012

- 1,011

- 0

Question:

Determine whether the function log(n

Definition in paint document if needed.

Solution:

n

log(n

Now, log(n)>log(2) whenever n>2. Therefore

log(2) + 2log(n)<3log(n).

log(n

∴Because there exists constants C and k such that log(n

Is this correct? The book says that log(n

Determine whether the function log(n

^{2}+1) is O(logn).Definition in paint document if needed.

Solution:

n

^{2}+ 1 < 2n^{2}whenever n>1log(n

^{2}+ 1) < log( 2n^{2}) = log(2) + 2log(n).Now, log(n)>log(2) whenever n>2. Therefore

log(2) + 2log(n)<3log(n).

log(n

^{2}+ 1) ≤ 3log(n) whenever n>2.∴Because there exists constants C and k such that log(n

^{2}+ 1)≤Clog(n) whenever n>k we can conclude log(n^{2}+ 1) is O(logn).Is this correct? The book says that log(n

^{2}+ 1) is not O(logn).