Need help disproving this

[Selena]

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

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.

 

[daon]

First, just a remark: g(n) is not a polynomial, but perhaps is still regarded as "polynomial time."

That said you wish to show for all constants c there is an n which satisfies |f(n)| > c|g(n)|. I.e. f will always "take longer" than running any number of g's for some input.