From:	George Foot <mert0407 AT sable DOT ox DOT ac DOT uk>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: The meaning of O(n)...
Date:	20 Jan 1998 22:58:23 GMT
Organization:	Oxford University, England
Lines:	42
Message-ID:	<6a3a6f$nao$3@news.ox.ac.uk>
References:	<bWLoegW7sFse-pn2-3vfQjsmVfXH4 AT localhost>
NNTP-Posting-Host:	sable.ox.ac.uk
Mime-Version:	1.0
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

On 20 Jan 1998 18:54:07 GMT in comp.os.msdos.djgpp Gili
<NOSPAMsl AT psycode DOT com> wrote:

: 	I have noticed that lots algorithms provide their efficency as O(n), 
: where N is the number of elements they are operating on. The last math
: course I have taken is Calculus 2 and I do not recall ever seeing the 
: O(n) function. What does it mean? How efficient is something with 
: O(n)? Thanks in advanced,

This isn't really on topic here.  For a good description of this
notation and its application to algorithms, I refer you to Knuth
volume 1 [1].  Briefly, though, O (big-oh) means `of the order of'.
Applied to algorithms, it means that the amount of work the algorithm
needs to do (i.e. the time taken) is of the order of whatever appears
in the brackets.  For example, the following algorithm (unoptimised)
is O(n):

for (i = 0; i < n; i++);

If it takes 1 second to complete with 1000 elements, then it will take
about 2 seconds with 2000 elements, and n/1000 (which is of the order
of n) seconds for n elements in general.  As further examples, the
following algorithms are both O(n**2) [** means squared]:

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++);

and

for (i = 0; i < n; i++)
    for (j = i; j < n; j++);

The O function can give you some idea of how efficient an algorithm is
-- it actually tells you how practical it would be to use an algorithm
with a large `n'.


[1] "The Art of Computer Programming volume 1: Fundamental
Algorithms", Donald E Knuth, published by Addison Wesley IIRC.

-- 
george DOT foot AT merton DOT oxford DOT ac DOT uk

- Raw text -