Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
If a function f1 is less than or equal a function g1, and a function f2 is less than or equal g2, does it follow automatically that f1f2 is less than or equal g1g2 as well? All of the above functions can only take natural numbers as arguments.
 2 years ago
 2 years ago
If a function f1 is less than or equal a function g1, and a function f2 is less than or equal g2, does it follow automatically that f1f2 is less than or equal g1g2 as well? All of the above functions can only take natural numbers as arguments.
 2 years ago
 2 years ago

This Question is Closed

windsylphBest ResponseYou've already chosen the best response.0
If not, please give a counterexample, or if there's some way this needs to be proved formally (rather than automatically following) please provide the proof. Thanks.
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
Assuming that since that the functions always produce natural numbers also, you can show this by an argument like so. Let f1 and f2 be maximal so that f1=g1 and f2=g2. Then, f1f2=g1g2 so the statement is true. Since f1 and f2 can't be any larger, we know f1f2 also can't be any larger. Thus, f1f2 must be less than or equal to g1g2.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
haha actually the functions should produce real numbers.. will this still hold? also, the main problem I'm working on actually involves proofs using the Big O notation. could you please also help me with that?
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
If they produce real numbers, greater than or equal 0, we're still good. But if the function can be less than 0, then let f1 and f2 be negative, g1 be negative, but greater than f1, and g2 be positive. Then f1f2 is positive, and g1g2 is negative, so f1f2 is greater than g1g2 and we have a contradiction. As for big O notation, i could try to help you with that, but I've had very little practice with that.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
haha thanks, here's the problem, my attempt at a solution, and a definition of Big O for your reference. I feel like my proof is somewhat iffy haha. http://dl.dropbox.com/u/17638088/prob2.PNG http://dl.dropbox.com/u/17638088/bigO.PNG
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
there appears to be a glitch on the problem 2 file, on that last part it should be f1(n)f2(n) = g1(n)g2(n). the equals sign looks like some mysterious character on the picture haha, maybe it's just the cursor beside it.
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
The proof looks good to me except for when you said that \[f_1 (n) \leq Ug_1(n)\]for all \[n \geq 1\]in the natural numbers. Unless I'm mistaken, the definition of Big Oh notation is that it's greater than or equal to some n', not necessarily 1. However, I don't think this should matter in the overall proof.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
Oh okay thanks, I chose n>= 1 because the functions can only take natural numbers as their arguments and natural numbers always start as 1. Would there be a problem with that?
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
Or should I just include in my proof that I let n_0 = 1??
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
Actually, I don't think it matters. When you combine the definition and f1(n) = O(g2(n)) there isn't any problem at all.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
I see, thank you. The next problem asks if problem 2 (this) holds even if g1 >= 0 and g2 >= 0. Would it? I'm thinking it would, since whatever f1 and f2 could be, they have to be less than g1 and g2 respectively in regards to Big O, and so f1f2 should still = O(g1g2). Please correct me if I'm mistaken.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
(problem 2 says that g1 > 0 and g2 > 0, in contrast to this problem where g1>= 0 and g2 >= 0)
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
I think it should still hold, since if it all equals 0, there's still no problem
 2 years ago

KingGeorgeBest ResponseYou've already chosen the best response.1
just be warned, some of my responses may be a little slow.
 2 years ago

windsylphBest ResponseYou've already chosen the best response.0
It's okay, thanks. I really appreciate your help.
 2 years ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.