• Support PF! Buy your school textbooks, materials and every day products Here!

Determine Big O of a function (Discrete math)

  • Thread starter Miike012
  • Start date
  • #1
1,011
0
Question:
Determine whether the function log(n2+1) is O(logn).

Definition in paint document if needed.

Solution:

n2 + 1 < 2n2 whenever n>1

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

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

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

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


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

Attachments

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
I think the book is wrong and you are right.
 
  • #3
Dick
Science Advisor
Homework Helper
26,258
618
Question:
Determine whether the function log(n2+1) is O(logn).

Definition in paint document if needed.

Solution:

n2 + 1 < 2n2 whenever n>1

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

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

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

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


Is this correct? The book says that log(n2 + 1) is not O(logn).
I think you are right and your book is mistaken.
 

Related Threads on Determine Big O of a function (Discrete math)

Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
0
Views
2K
Replies
4
Views
2K
Replies
10
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
1K
Top