At some point in college everyone learns worst-case complexity

analysis. And for some obscure reason, almost everyone immediately

decides that it’s the perfect tool for studying the behaviour and

comparing the performance of algorithms. This is wrong. Just wrong.

1 – Worst-case complexity analysis gives you exactly what the name

implies: a majoration (order of magnitude) of the worst possible

case.

Unless that result is proven to be tight, i.e., there is an

example of some input that actually makes the algorithm achieve

the worst case, you can’t really be sure of anything. If a

procedure is O(n^2), it is also O(n^3); you need the tightest

possible order, not “the best currently known result”. Thus,

unless you can also tell something about the best-case complexity

— which is usually ignored — you may be avoiding an O(n^3)

algorithm that someone will one day prove to be O(n^2).

2 – Lets assume, for the sake of argument, that a given algorithm A is

O(n^2), and that this result is tight. Two questions arise:

a) How frequently does this happen?

Knowing that there exists some input on which algorithm A will

behave quadratically doesn’t really tell you much. You need to

know more, specifically about the conditions on which *you* are

going to apply the algorithm.

For one, even if you must assume random input, and thus the

possibility of achieving the worst possible case, unless you

know that it occurs frequently, you may probably apply the

algorithm safely. Take for example the simplex algorithm. It’s

exponential in the worst case, but the worst case is so rare

that it is one of the most popular algorithms for linear

programming. You must also consider the particular environment

on which you are go use the algorithm. If you actually take

some time to think, you will find out that on several occasions

you have to consider only a subset of all possible inputs, and

maybe avoid the worst possible scenario.

b) How big is your *real* input?

Remember that the big O notation provides only an upper bound

on the growth rate and assumes that the size of you input will

tend to infinity. Now seriously, does the input of your

algorithms always go to the infinity and beyond? So why are you

choosing the perfect algorithm for a harder scenario?

3 – Constants can make a big difference

We always throw away constants when doing worst-case

analysis. They are useless, right? Well, I disagree. Consider

two algorithms, A1 and A2, such that A1 is O(n log(n)) and A2

is O(n^2). It’s pretty simple, right? A1 is faster than

A2. Well, think again, but this time a little harder. Actually,

what you know is that the asymptotic growth of A2 surpasses

that of A1. This analysis assumes that the size of the input

tends to infinity. What if you know that you will never have an

input such that n>100? What if on top of that, that big O

notation is hiding the constants 8 from A1 and 1/8 from A2?

Suddenly, in real life, a quadratic algorithm is faster than a

logarithmic one…

And for the record, I have a pretty good example of this

scenario using finite automata: a DFA with 100 states is huge

on many setups. A blind implementation of the “fastest n log(n)

algorithm” can be rather disappointing when compared to a

simple quadratic approach.

My point is: worst-case complexity analysis is a tool. Just as

best-case complexity, average-case, amortized analysis, etc. It is a

good thing to know it and to use it, but by all means it’s not the

answer to all problems!

Blindly choosing an algorithm simply based on a worst-case complexity

result will probably do you more harm than good. When implementing an

algorithm, it is crucial to know you setup: what kind of input can you

expect, equivalent algorithms available, tailor-made options, specific

optimizations, hardware you will be using, etc., etc.