A community for students.
Here's the question you clicked on:
 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 nO(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!
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 nO(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

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0He 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0When 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.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!!

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Yeah, and I should be clear I mean the _relative_ distance between them will become infinitesimally small as compared to their values.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Yes I gathered that much. Thanks again!

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0How 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Pessimistic indeed. Thanks for clearing that up. I was probably skimming through everything too fast yesterday. =)
Ask your own question
Sign UpFind more explanations on OpenStudy
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.