A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Hello. I am confused about a statement the professor makes in Lecture 8 of MIT 6.00: at around 20:04 in the video he states that order of growth of the discussed problem is O(n*m)--- then continues to say "and if m were equal to n---O(n**2)--its quadratic." Why does he assume that m will be equal to n? An explanation of that whole section involving the complexity of example 4 would be greatly appreciated!

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    He isn't assuming as much as making a hypothetical. It's still a complexity where Something is being multiplied by something, the assumption simply make it easier to say O(n**2) instead of having two different variables. I watched that lecture several times and worked through the math. I suggest you take it step by step as well. Any particular questions you have you can pose here.

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    When you're talking about the asymptotic behavior of an algorithm you're thinking about what happens when the size of the input approaches infinity. In the case of two inputs you can assume that both are growing, so it's fair to say that the difference between them will approach 0 as they approach infinity. Hence setting them equal to each other is a valid simplification.

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Nikola: I was working through the math however that the point where I got lost. @Polpak: Thank You!! You pin pointed and addressed exactly what I was missing. Having gone through the math treating n and m as if they were fixed variables caused me to lose sight of the fact that Big O is referring to the rate of growth of an algorithm's complexity as n and m GROW. My mistake was that I was imagining n and m as being two arbitrary values. So again thank you for clearing that up!!

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, and I should be clear I mean the _relative_ distance between them will become infinitesimally small as compared to their values.

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes I gathered that much. Thanks again!

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How is the size of the input going to approach infinity if the field is in an array limit for a preset number of characters? Note, this excludes integers because numerical expressions can be denoted or expressed as seeminly infinite. Realize it is hypothetical please, and that a control/arithmetic unit cannot process an expression involving infinity without a bit denoting infinity. It is just impossible. -_- Maybe I misunderstood something here.

  7. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think the point polpak was getting at is that for sufficiently large inputs (n and m) n*m might as well be n**2 since the difference between them is insignificant in comparison to the size of the large inputs themselves. No one is saying that the input can actually go to infinity, but for the purposes of algorithmic analysis we can use infinity as the limit to project a worst case scenario (even if this case isn't actually possible). The result is a safe yet pessimistic analysis.

  8. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Pessimistic indeed. Thanks for clearing that up. I was probably skimming through everything too fast yesterday. =)

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.