anonymous
  • anonymous
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.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
The proof looks good to me except for when you said that \[|f_1 (n)| \leq U|g_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.
anonymous
  • anonymous
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?
anonymous
  • anonymous
Or should I just include in my proof that I let n_0 = 1??
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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.
anonymous
  • anonymous
(problem 2 says that g1 > 0 and g2 > 0, in contrast to this problem where g1>= 0 and g2 >= 0)
KingGeorge
  • KingGeorge
I think it should still hold, since if it all equals 0, there's still no problem
KingGeorge
  • KingGeorge
just be warned, some of my responses may be a little slow.
anonymous
  • anonymous
It's okay, thanks. I really appreciate your help.

Looking for something else?

Not the answer you are looking for? Search for more explanations.