Beyond Big-O in AdventOfCode
Many of the problems in AdventOfCode involve finding ways of handling a problem that is suddenly too large to handle by the naïve approach (which part1 often cleverly tries to lull you into). Most fundamentally, the first thing to do is to find an algorithm with a better Big-O complexity. What that means, simplistically, is that given an input as a list of size N, what power of N number of operations do you need to do? A simple math formula is O(1), or constant time, an iteration through the list is O(N), or linear time, comparing each element against every other is O(N^2), or quadratic time, and so on. Sorting is O(N log N), so somewhere between O(N) and O(N^2). Some problems are very bad where you end up with N as the exponent in exponential time. In this post I want to look at what can be done beyond finding the "optimal" algorithm in Big-O terms. It will mostly be about shaving a little bit more performance, but I also want to look at aspects of beauty, simplicity and cl...