From: Luis Hernandez <newton AT math DOT gatech DOT edu>
Message-Id: <199801211908.OAA26601@math05.math.gatech.edu>
Subject: Re: The meaning of O(n)...
To: djgpp AT delorie DOT com
Date: Wed, 21 Jan 1998 14:08:18 -0500 (EST)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Precedence: bulk

    I'm sending this answer to the list, 'cause there was a problem
    with this person's email address.
                                      Luis 

> 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

  There  are  at least two similar symbols o() and O(),  and their meanings
  are  not exactly the same (but some people use O() when refering to o()).
  Those o-symbols are not functions, they are  used to represent classes of
  functions.

  For example, you say that f(x) = o(g(x)) as x --> a if lim f(x)/g(x) = 0
  as x-->a. (sin(x) = o(1) as x-->0, but sin(x) is NOT o(x) as x-->0).
  
  On the other way you say that f(x) = O(g(x)) as x-->a if |f(x)/g(x)| <= K
  as x-->a for some constant K. (sin(x)=O(x) as x --> 0).
  (Note: in the previous statments 'a' can represent infinity)

  So, for example, if some process' time of conclusion  is O(n), where n is
  the  quantity of elements it is  operating on, then  that means that that
  process' running time depends linearly on that number.

  For example, if some process require  O(n^2) memory units, where n is the
  quantity  of elements   it  is operating  on, then that  means  that that
  process is "spending" K*n^2 memory units to "run", for some constant K.

  So, an  "ideal"  algorithm is one that requires less ;-) than O(n) memory
  units, and runs in less than O(n) time, etc.

  Hope this helps,

--------------------------------------------------------------------------
Luis Hernandez. email: newton AT math DOT gatech DOT edu  329805 Georgia Tech Station
Math School, Georgia Tech.                          30332 Atlanta, GA, USA
--------------------------------------------------------------------------
                     "I don't want to achieve inmortality through my work,
                          I want to achieve inmortality through not dying"
                                                               Woody Allen
--------------------------------------------------------------------------
"I'm going to live forever or die trying"
Digital Hippie
--------------------------------------------------------------------------