Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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?

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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?

Answer 9

Or should I just include in my proof that I let n_0 = 1??

Answer 10

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.

Answer 11

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.

Answer 12

(problem 2 says that g1 > 0 and g2 > 0, in contrast to this problem where g1>= 0 and g2 >= 0)

Answer 13

I think it should still hold, since if it all equals 0, there's still no problem

Answer 14

just be warned, some of my responses may be a little slow.

Answer 15

It's okay, thanks. I really appreciate your help.