Wednesday, August 31, 2016

RAM isn't O(1)

A recent post benchmarked the actual running time (not number of instructions) for a number of algorithms and found that the lack of accounting for the effects of caching made the graphs lie. It seems most accurate to multiply your algorithm's classic running time by the square root of N.

How sobering.

No comments:

Post a Comment