Wrote some code in C but I could only do as well as O(n^2), but that's because I was concerned about linear cache misses and pushing more registers onto the stack with function calls.