Re: Big oh Notation

From: Moth (not_at_this.address)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 21:01:01 GMT

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.

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: Probabalistic algorithms.
    ... > where do you see probability in quicksort? ... > Can you make a sort algorithm both faster and more secure than a ... The problem with QuickSort is supposed to be the stack depth, ...
    (comp.lang.pascal.delphi.misc)
  • Re: Probabalistic algorithms.
    ... >where do you see probability in quicksort? ... >Can you make a sort algorithm both faster and more secure than a ... >(I agree that recursive quicksorts in theory might cause stack overflows ...
    (comp.lang.pascal.delphi.misc)
  • Re: FastCode Sort: Multi-threading
    ... > Has anyone else tried this out with a quicksort? ... I'm wondering because I very nearly have a multi-threading ... since a sort algorithm doesn't have to wait for ... it purely depends on CPU power and memory speed. ...
    (borland.public.delphi.language.basm)
  • Re: Quicker then QuickSort???
    ... > I might be a bit niave here but I was looking over a quicksort ... The fastest sort algorithm is the bubble sort with flag. ... If you have sorted lists, yes, quick sort is the wrong answer. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Probabalistic algorithms.
    ... where do you see probability in quicksort? ... Can you make a sort algorithm both faster and more secure than a ... (I agree that recursive quicksorts in theory might cause stack overflows ...
    (comp.lang.pascal.delphi.misc)