Hacker News Reader

Comment by pufuwozu | Hacker News Reader

Author here. Sadly our WordPress didn't have caching enabled so here's a Gist of the content:

https://gist.github.com/pufuwozu/5095510

FTA: "Well, hopefully we almost always want the asymptotically optimal algorithm to solve our problem. You might have noticed that the above code is selection sort - an algorithm with best/worse/average time complexity of O(n^2)."

"Sadly, we can't write a test or a type to satisfy our specification. We need to actually perform some (asymptotic) analysis to derive our code, instead of relying on tests!"

Algorithmic complexity is not measurable by the test code, but its also not measurable by your customers. So why measure it? Instead, write a test for something that your customers do care about: performance perhaps? Its easy to throw a huge array at it and see if its too slow.

For one, you would have to throw arrays of different sizes at it and produce a plot to see O(n^ 2) type growth. But in general that still doesn't tell you what the complexity analysis does. The worst case could depend on a particular input type. E.g. one containing a particular pattern. You won't know to test that without doing the analysis though.

Also, worst case complexity is certainly measurable by customers. They notice when your product becomes usably slow either over time or perhaps suddenly when given a particular input.

It's not a complex algorithm, it's a static website run from wordpress that could be faster by any of these: S3, CloudFront, memcache, APC, or even file caching.

Yes, you could spin up any number of AWS to throw ab / httperf traffic at it, but why? HN has demonstrated how inadequate their server solution is.

It's too slow. Now what?

You have to use asymptotic analysis to figure out that it's O(n^3) but can actually be performed in O(n) - then write the derived code from your analysis. Nothing has changed.

Customers care; transitively.

Reply on news.ycombinator.com