r/MathHelp•
Zestoid

Help with Bog-Oh proof

I've been working on the following proof for a while but havent gotten very far. I think I need to utilize f(1)/g(1) as my C value in proving the Big-Oh relationship.

Prove that, for f:N→R+,g:N→R+, if f(n) is monotonically decreasing and g(n) is monotonically increasing, then f(n)∈O(g(n))

I want to prove this using the defition of Big Oh. So, I need to show that there exists a C and c, both positive, such that f(n) <= C * g(n) for all n>=c

I just realized that I mispelled Big-Oh in the title, my bad.

Posted Dec 16, 2019, 7:09 PM UTC · edited

25
funkapalooza•

You practically have the answer already. With f(1)/g(1) = C, you know that C * g(1) = f(1), which also implies f(1) <= C * g(1), since, you know, less than OR equal to.

Since g is monotonically increasing, you know that the rest of the C * g(n) s are also necessarily at least as big as your f(n)s. That's basically your whole proof right there, you practically had it all figured out when you were posting the question, good work my dude

2
funkapalooza•

Also the fact that f is monotonically decreasing also needs to be mentioned in the proof, because if it weren't, than it might outpace g in growth, if that makes sense

1
ZestoidOP•

Thanks for the help! I have a few questions though. How would I formally show that C = f(1)/g(1). I understand it logically as I came up with it in my own but how do I show this formally?

1
funkapalooza•

Ah, that's the thing, you don't need to show that C equals that. You literally just say "define C = f(1)/g(1)" To prove f is O(g), you just need to come up with literally any big C and little c you want, and then show that the conditions hold ( the conditions you posted in your original question). C could also be 2 * f(1) / g(1), or three times that, or really anything. You just need to show that for SOME big C and lil c, that those conditions hold. If you can come up with and C and c, then you've already solved the problem.

1
AutoModeratorMOD•

Reminder:

  • What have you tried so far? (See Rule #2)

  • Please don't delete your post. (See Rule #7)

We, the moderators of r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1