 #1
 1,011
 0
Question:
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>1
log(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).
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>1
log(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).
Attachments

8.1 KB Views: 787