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.
