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
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
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
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?
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.