Determine Big O of a function (Discrete math)

[Miike012]

Question:
Determine whether the function log(n²+1) is O(logn).

Definition in paint document if needed.

Solution:

n² + 1 < 2n² whenever n>1

log(n² + 1) < log( 2n² ) = log(2) + 2log(n).

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

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

log(n² + 1) ≤ 3log(n) whenever n>2.
∴Because there exists constants C and k such that log(n² + 1)≤Clog(n) whenever n>k we can conclude log(n² + 1) is O(logn).


Is this correct? The book says that log(n² + 1) is not O(logn).

 

[Office_Shredder]

I think the book is wrong and you are right.

 

[Dick]

Question:
Determine whether the function log(n²+1) is O(logn).

Definition in paint document if needed.

Solution:

n² + 1 < 2n² whenever n>1

log(n² + 1) < log( 2n² ) = log(2) + 2log(n).

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

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

log(n² + 1) ≤ 3log(n) whenever n>2.
∴Because there exists constants C and k such that log(n² + 1)≤Clog(n) whenever n>k we can conclude log(n² + 1) is O(logn).


Is this correct? The book says that log(n² + 1) is not O(logn).

I think you are right and your book is mistaken.