Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

@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!!

Answer 4

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

Answer 5

Yes I gathered that much. Thanks again!

Answer 6

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.

Answer 7

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.

Answer 8

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