Newsgroups: comp.os.msdos.djgpp
From: "A. Jans-Beken" <jabe AT oce DOT nl>
Subject: Re: The meaning of O(n)...
Content-Type: text/plain; charset=us-ascii
Message-ID: <34C5BF2B.1159@oce.nl>
Sender: news AT oce DOT nl (The Daily News @ nntp01.oce.nl)
Content-Transfer-Encoding: 7bit
Organization: Océ-Nederland B.V.
References: <bWLoegW7sFse-pn2-3vfQjsmVfXH4 AT localhost>
Mime-Version: 1.0
Date: Wed, 21 Jan 1998 09:26:03 GMT
Lines: 53
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

In an array or list 'N' represents the number of elements.

   For example: 
      int x[100] 
   has 100 elements.

O(n) means that an algorithm takes some time that is constant for each
element. Hence the processing time of the complete array/list depends
only on the number of elements in it.

   For example:
      for (int i = 0; i < 100; i++) cout << x[i];
   has an efficiency of O(n).

O(n^2) means that an algorithm takes some time proportional to the
number of elements TO THE POWER OF TWO which is a very bad efficiency
for large number of elements.

   For example:
      for (int i = 0; i < 100; i++) 
         for (int j = 0; j < 100; j++) 
            cout << x[i] << "-" << x[j];
   has an efficiency of O(n^2).

Very efficient algorithms may be of efficiency O(log N). Think of binary
search trees for example. In such an algorithm NOT EVERY ELEMENT must be
checked and the complexity is therfore LESS than N.

Final note:
When in a loop you must perform 2 operations on each element than the
efficiency is O(2n). Altough it is less efficient then O(n) it is common
practice to say that O(2n) is the same order of efficiency as O(n). 

   For example:
      O(100)     =   100 operations for the algorithm.
      O(2.100)   =   200 operations for the algorithm.
      O(100^2)   = 10000 operations for the algorithm.
      O(log 100) =     2 operations for the algorithm.

It is clear that a log algorithm is preferred when possible (altough
software is commonly more complex to write).