5 ms·
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 sca
by shred45 11y ago
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.
- 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.