Big-O notation (was: Re: Python and Schools)

Andrew Koenig ark at research.att.com
Wed Apr 16 00:03:16 CEST 2003


Mike>     Characterisation of an algorithm's (as distinct from an
Mike>     implementation's) performance in relation to the size of the input
Mike>     set.  Normally of interest in determining the
Mike>     scalability/suitability of a particular algorithm.  The static (e.g.
Mike>     setup) and proportional (e.g. implementation) factors in the
Mike>     algorithm are factored out under the assumption that they are
Mike>     swamped by the relative effects of the size of the input set as that
Mike>     goes to infinity.

Also, big-O notation always refers to an upper bound, not an estimate
that might be high or low.  So, for example, every quantity that is
O(N) is also O(N log N), but the reverse is not true.

Mike> Common examples of big-O performance types:

Mike>     * O(1) -- time is linear, that is, it takes the same amount of time
Mike>       to do something regardless of how large the input set is.

O(1) doesn't mean linear, it means bounded by a constant.  That is,
if the running time of an algorithm is O(1), it means that there exists
a time interval t such that the algorithm always finishes in time < t.

Mike>     * O(log N) -- time grows as the log of N, (for those who don't
Mike>       remember high-school math, this means that it grows very slowly
Mike>       compared to N).

You can also think of O(log N) as being no worse than proportional to
the number of digits in N.

Mike>     * O(N) -- time grows linearly as the size of the set grows (e.g.
Mike>       process every item in the set in turn)
Mike>     * O(N log N) -- see O(N) and O(log N), basically, you do an amount
Mike>       of work tied to the size of the whole set for every stage in an O(
Mike>       log N ) operation (this is comparatively rarely discussed in my
Mike>       experience).

Many sorting  algorithms are O(N log N).

Mike>     * O(N**2) O(N**3) etceteras -- time grows as an exponent (e.g.
Mike>       2,3,3.4,10) of the size of the set, so you get geometric explosion
Mike>       of running time as set size increases.  These algorithms tend to
Mike>       fail on even small N values.

Mike> You can have all sorts of fun learning how to combine and
Mike> re-factor the equations to get a final big-O notation, but for
Mike> the most part, practical coders can get away with recognising
Mike> and avoiding O(N**X) where X > 1 situations.  Recognising the
Mike> underlying patterns in O(log N) (binary searches and the like),
Mike> and O(1)-ish situations is useful as well, as they provide very
Mike> good general scalability.  The calculus of big-O notations is
Mike> just a convenient shorthand for people doing rigorous analysis
Mike> AFAICS.

O(N**1.5) is often bearable.

Mike> Keep in mind that the setup and constant factors of the
Mike> algorithm are factored out of the equations.  Something which is
Mike> O(1) may be slower than O(N**3) for all practical values of N if
Mike> the setup time for the O(1) algorithm approaches the age of the
Mike> universe.  Similarly, two algorithms which are O(N), but with
Mike> vastly different constant factors (implementations) may have
Mike> dramatically different running times.

Right.


-- 
Andrew Koenig, ark at research.att.com, http://www.research.att.com/info/ark




More information about the Python-list mailing list