Hah!

So it looks like my original timing simulations were pretty accurate, the crossover point for the new code being faster is looking like somewhere between 40-60 bases, which is even lower than I'd originally thought, and within the error bars for my data to agree with the other random sequence data.

Which is probably meaningless to anyone reading this. Roughly, my new program can be compared for some cases to a previous incarnation (not written by me), and for longer sequences should be much faster (the time complexity is lower by at least a factor of n). For short sequences, the older program has a speed advantage because it has a caching system which, when it is working, can actually be effective for really short sequences. (It's pretty much useless for long sequences). I originally did some data on short notice, which suggested that at 50 bases the older program was faster, but at 100 the new program was faster, and for longer lengths there wasn't even a comparison (older program went exponential above 100, mine stayed linear til about 1k). Another person using my program to do some timing got results which were very strikingly different, suggesting that the crossover point was above 100 before mine even broke even. They had a lot more time to actually run sims (I had a few days and was out of town for a while), and so they had more data points to work with. After meeting up with them today and talking, I decided to run a much more exhaustive look at the appropriate ranges, and the data now supports a crossover near 50 pretty well. Happy. I wish I could push it lower though, theoretically I should be able to, but it may involve some nasty coding which I don't want to spend time on.