The primary beneficiary of the O(N) solution isn't the computer; it's you. The O(N) solution, if you know how to do it, is faster and easier to write, easier to reason about, and easier to extend. (The actual problem was slightly more involved than this gloss, as it often is.)
-
-
Show this thread
-
(If you're wondering what this O(N) vs O(N^2) thing means: it's notation used in computer science to describe the asymptotic time complexity of an algorithm. That's a mouthful. In less specialized language, the distinction is "Do I have to compare every item to every other one?")
Show this thread -
"How do you tell than a list with 100,000 words in it doesn't include a duplicate without checking each word against every other word, Patrick?" Excellent question! Answer: you stuff each word as you're checking it into hash table and then you only have to go through list once.
Show this thread
End of conversation
New conversation -
-
This Tweet is unavailable.
-
-
You forgot the O(NlogN) way, which is a 1 liner in either shell script or sql. Also, the O(N) way has some caveats.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.