Re: Big oh Notation

From: Yoyoma_2 (Yoyoma_2_at_[at-)
Date: 02/25/04 

Date: Wed, 25 Feb 2004 16:20:37 GMT

Moth wrote:
> Big O is pretty simple. The O stands for "the Order of" and it shows the
> general number of comparisons needed in a sort algorithm. For example, the
> average number of comparisons for a selection sort is =N^2/2-N/2. In this
> case the N^2 dominates and so the big O notation is O(N^2). For a quicksort
> I believe it is =N(log2N) which defined as O(log2 N) because the log2N,
> against a large number of items, will dictate the amount of time taken.

Oh just a little thing you missed i think. Big O notation is the "Worst
Case" notation. Meaning that the worst case is what is going to happen
after the O. For example, the worst case in picking a number of an
array with a simple for loop is O(n). Because n (the number of
elements) is the worst-case scenario (that the number you want is at the
end).

There are two other notations. Big-Omega (I don't have the omega
symbol, but its like the Ohms symbol if you remember that from
electronics) means the best case scenario. For example, if your
element is at the begining of the array.

Now there is another one that talks is 'tight-bound'. This is your
"average" case and is the best to compare two algorithms. Since an algo
could be excellent, but have one very bad case, O notation only shows
the worst case. But the Big-Theta notation shows the average case.

If you are a beginner you can compare with O notation to algorithms, but
if you have done this before or have some math background, i would
suggest comparing with Big-Theta.

For a good site, its usually mathematics sites that have it. Here our
class book. This is probably what you might be you are looking for.

Cormen, Leiserson, Rivest, and Stein: "Introduction to Algorithms",
McGraw Hill, MIT Press.

Or any good Discreet Math book will have it.

>
> Hope this helps a bit.
>
>
> "jova" <Email@nospam.net> wrote in message
> news:fL9_b.43099$M8.3955@nwrdny02.gnilink.net...
>
>>Does anyone know of a good site where I can learn of this?
>>
>>
>
>
>

Relevant Pages

  • Re: Similarity searching
    ... a factor of N*log, if the arrays are big you won't in general have to compare to the last element so I don't see the factor of L**2, and I don't see where that C**2 factor is coming from at all. ... There are also sorting algorithms which don't compare each item to every other item, yet still generate a sorted result. ... Similarity searching is still an active science, but there are a lot of useful algorithms out there now. ...
    (comp.lang.fortran)
  • Re: Similarity searching
    ... a factor of N*log, if the arrays are big you won't in general have to compare to the last element so I don't see the factor of L**2, and I don't see where that C**2 factor is coming from at all. ... There are also sorting algorithms which don't compare each item to every other item, yet still generate a sorted result. ... If electricity comes from electrons, ...
    (comp.lang.fortran)
  • Re: Similarity searching
    ... a factor of N*log, if the arrays are big you won't in general have to compare to the last element so I don't see the factor of L**2, and I don't see where that C**2 factor is coming from at all. ... There are also sorting algorithms which don't compare each item to every other item, yet still generate a sorted result. ... Dynamic programming algorithms are popular if you need the best approximate match. ...
    (comp.lang.fortran)
  • Re: Parameterbeschreibung mathematischer Formeln
    ... "Binary algorithms arise so frequently, it is wise to have a shorter ... Laut David Kastrup begegnet man bei Informatikern der Notation ... Laut Herbert Voss begegnet man in der Mathematik und der ...
    (de.comp.text.tex)
  • Re: Big O and algorithm to decide string A contains string B?
    ... >contains String B. ... It depends if A is semi-const or B is semi-const. ... pages, just for start -- KMP and BM algorithms, those are "simple" ... There are also algorithms based on such idea -- first you compare two ...
    (comp.programming)