Re:The Deceptive Anagram Question
by shred45 on Wednesday April 15, 2015 @03:23PM
(#9383436)
Can someone explain the comment about how quadratic time complexity does not scale?
[ Parent
| on HN ]
Re:The Deceptive Anagram Question
by crimsonalucard on Wednesday April 15, 2015 @03:32PM
(#9383491)
Good question. I just want to mention that this is a fact that a student with a degree in computer science should absolutely know.
I'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.
I 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.
Ah, this makes much more sense, thanks.
Re:The Deceptive Anagram Question
by gamesbrainiac on Wednesday April 15, 2015 @08:20PM
(#9385155)
I 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.
The 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/lec...
Imagine 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.