Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

windsylph Group Title

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
  1. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  2. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  3. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  4. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  5. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  6. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  7. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 2 years ago
  8. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  9. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  10. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  11. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  12. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  13. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 2 years ago
  14. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 2 years ago
  15. windsylph Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
    • Attachments:

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.