From: swarsmatt AT aol DOT com (SWars Matt)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: The meaning of O(n)...
Date: 23 Jan 1998 22:23:35 GMT
Lines: 24
Message-ID: <19980123222300.RAA20267@ladder01.news.aol.com>
NNTP-Posting-Host: ladder01.news.aol.com
Organization: AOL http://www.aol.com
References: <34C50E15 DOT 5067 AT cornell DOT edu>
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

>Gili wrote:
>> 
>> Hi,
>> 
>>         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,
>> 
>> Gili

I know this is off-topic, but I'm going to answer the question anyway. In a
mathematical sense, something that is O(f), where f is some function, does not
increase as fast as f as n->infinity. It is 'asymptotically dominated' by f, or
stays less than f. For an algorithm, say a sorting algorithm, it's basically
the number of comparisons to sort n things.
So an O(n) algorithm is better than O(n log n) or O(n^2). (This may be
confusing if you see things about Taylor series where O(n^2) or O(n^3) are
taken to be negligible because they're very small - in that case they're
proportional to a power of a number with abs. value less than 1, so they are
very small.)
For more about O, o, asymptotic dominance, etc. look for a discrete math book.