Saturday, October 13, 2007

Every n matters

When you study computer science and you start learning algorithms, you are introduces to the O(n) concept, meaning there is a different between an algorithm that takes linear time (1 second for 1000 items, 2 seconds for 2000 items and so on) and an algorithm that takes exponential (2 to the power of n) time, meaning it's a very inefficient algorithm.

Although this lesson is important, there is a darker side to this kind of thinking - you tend to ignore efficiencies with the same order of magnitude, meaning an algorithm with 10n efficiency and 80n efficiency are the same to you, even the first is 8 time faster than the second. This means that if you choose the first a certain procedure may cause the user to wait 250 milliseconds, while the second will delay the user for 2 whole seconds - big difference.

So don't consider to n values to be similar just because they are within the same order of magnitude.

No comments: