Big-O notation

[Mike C. Fletcher]

Andrew Koenig wrote:

>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.
>
I seldom seem to see people invoking that part of the definition, though 
it's definitely it.

Mostly people seem to talk about the best, average and worst-case 
performance as if the O notation was relevant in each case, though IIUC 
the worst-case would be the "real" O description.  That is, the O 
notations seem to be commonly used as shorthand notation for "constant 
running time", "linear running time", "quadratic running time" 
etceteras.  Bad people, bad :) .

>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.
>  
>
Yup, I'd meant to write constant and brain-fog occluded the shore

...

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

>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
>  
>
...

>O(N**1.5) is often bearable.
>

Good point.
...

Okay, so now we have "The Practical Coder's Guide to big-O Notation" :) 
.  We rock ;) ,
Mike

_______________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://members.rogers.com/mcfletch/