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

Need help disproving this

  • Thread starter Melodia
  • Start date
  • #1
18
0

Homework Statement



Thanks for the help on the last problem. Here is the final problem set I'm stuck on:


SYPzV.jpg


Homework Equations





The Attempt at a Solution



To me it seems that there will always be a positive c so that cg(n) is greater or equal to f(n). No matter how large n is, since there's no limit to how large c can be (can even be a decimal), wouldn't that always be possible?

Thanks.
 

Answers and Replies

  • #2
33,484
5,174
First off, g is not a polynomial, as it is not the sum of multiples of integral powers of n. It might be helpful for you to graph the two functions, because you would see that for n larger than about 20, the linear function dominates the other function. Although f(n) = 2n + 3 is a linear function and grows at only a constant rate, that rate is larger than that of the other function, for large enough n.
 
  • #3
18
0
Oooh I see. Since c is fixed and chosen before the n, then there will always be an n that contradicts the statement right?

I'm guessing the same thing applies to this other problem right?

8cBSM.jpg
 
Last edited:
  • #4
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,617
1,252
Yes, essentially. For the first problem, there's no fixed value of c that works because you can always make n large enough so that the inequality doesn't hold. In other words, no such c exists.
 

Related Threads on Need help disproving this

Replies
9
Views
2K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
918
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
23
Views
1K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
711
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
Top