There are a lot of great answers here. Let me add another one I really love: the Knuth Morris Pratt algorithm for string matching. There are many features about

There are a lot of great answers here. Let me add another one I really love: the Knuth Morris Pratt algorithm for string matching. There are many features about it I especially love. First of all it takes a simple idea (when a mismatch occurs it's often possible to shift the pattern a lot more than just by one position) and takes it to it's logical conclusion (that of defining and computing the so called border lengths of prefixes). Second, the analysis of the precomputation step (the border lengths) is tricky, and amortised, but plainly obvious once you see it. It shows the importance of making a good definition and thinking differently (for the run time analysis I thought for a while and failed to come up with an argument why it runs in linear time, but once you see it differently it's obvious :)) I only recently had the chance to understand this algorithm. Here's a little (annotated) gist I made after understanding it: https://gist.github.com/quantumelixir/3c410dd4a0afe0f2514e0f554cddab05 https://gist.github.com/quantumelixir/3c410dd4a0afe0f2514e0f...