3 ms·
Can someone explain the comment about how quadratic time complexity does not scale?
by shred45 11y ago
Can someone explain the comment about how quadratic time complexity does not scale?
- gnur 11y agoImagine you need to compute a list that takes a second to calculate, a list that is twice as long will take 2^1=2 seconds, a list that is 10 times as long will take 2^10=1024 as long, if the list gets 100 times as long, it will take so long that the universe will probably have burned out by then.
- shasta 11y agoQuadratic: f(x) = x^2 Exponential: f(x) = 2^x
- crimsonalucard 11y agoGood question. I just want to mention that this is a fact that a student with a degree in computer science should absolutely know.
- shred45 11y agoI'm getting the impression that the number of facts that I should be ashamed of not knowing is O(n!) where n is the unix time stamp. That definitely doesn't scale. But more seriously, I think I worded my question poorly. I understand why O(n^2) is not ideal. The author's statement was: "for more computing power we throw at this the slower it gets per computer." Now I'm not sure how he would seek to throw computing power at the algorithm, but I can immediatly think of a parallel implementation of this algorithm with efficiency O(1), at least for p<=n. So my question is, why does a quadratic algorithm neccesarily imply diminishing returns when you add more computing power? That is how I interpreted his sentence and it is not clear to me.
- aetherson 11y agoI think that the author phrased himself clumsily or (less likely) misunderstands O-notation. My guess is that he intended to say, "As the problem gets bigger, throwing more computing power at it gets less and less efficient," and got tripped up in the words.
- shred45 11y agoAh, this makes much more sense, thanks.
- gamesbrainiac 11y agoI am terribly for the failure of an illustration I provided. I'm sorry I didn't see this sooner, or I would've jumped at a second chance to explain. I assure you, I'll try to do better in the future.
- giech 11y agoThe idea is that as time goes by, computers become twice as fast (Moore's law), but problems also become twice as big. With a quadratic algorithm, you will need twice as much time to solve the problems of the bigger size, even on the faster computer. See page 22 of http://www.cs.princeton.edu/courses/archive/spr15/cos126/lectures/41analysis.pdf http://www.cs.princeton.edu/courses/archive/spr15/cos126/lec...