Algorithms: Design and Analysis, Part 1 is a free online course from Standford offered through Coursera.org. An assignment that stuck with me was implementing an algorithm for counting inversions. Counting inversions is a way to quantify similarity of two ordered lists. The canonical example described in the lectures was comparing lists of favorite movies.
I banged out a naive implementation using nested loops that I could use for comparison to make sure I was implementing the real algorithm correctly.
1 2 3 4 5 6 7 8 

The algorithm described in lecture is a divide and conquer algorithm based on a variation of merge sort, and as you might expect from its lineage, runs in O(nlog(n))
time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

* The guts of the implementation are not shown per the Coursera honor code.
The assignment was to run this algorithm on a list of 100,000 integers and report the number of inversions. I ran both implementations as a sanity check.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

It’s one thing to crunch numbers on a calulator or plot graphs to gain an intuition for algorithm complexity, but it’s quite a bit more meaningful to wait for 15 seconds while a 2.7GHz quadcore Intel Core i7 grinds through ~5 Billion comparisions O(n^2)
versus a mere 140 ms to zip through 1.6 Million comparisons using an O(nlog(n))
implementation.
Yeah, science!