Re: Big oh Notation

From: Silvio Bierman (sbierman_at_idfix.nl)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 22:43:21 +0100

"Moth" <not@this.address> wrote in message
news:hSt_b.73223$Wa.26732@news-server.bigpond.net.au...
> 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?
> >
> >
>
>

If only we had a sorting algorithm of O(log2N) :-) Unfortunately both N and
log2N are significant here (N is more then log2N anyway) so you get O(N
log2N).

And for QS that is average behaviour, worst case is O(N^2) also. For a
sorting algorithm with worst-case O(N log2N) you would need something like
HeapSort.

BTW: Big O notation is used for any algorithm category, not only for sorting
algorithms.

Silvio Bierman

Relevant Pages

  • Re: Help me with references
    ... > about the problemspace that the general quicksort algorithm doesn't. ... but again you shouldn't choose bubble sort for these few cases. ... >> best choice for a sorting algorithm in a real machine. ...
    (comp.lang.java.help)
  • Okay to move an "object" will-nilly?
    ... though there may in fact be a negative effect), ... C++ to move an object in memory, i.e. simply re-locate it. ... I wrote a funky kind of algorithm for sorting an array (whether ... code such as a sorting algorithm, you DON'T just re-locate objects willy- ...
    (comp.lang.c)
  • Re: C Sharp sorting considered superior to C by an order of magnitude
    ... be sorted by algorithm A" is nonsense. ... sort many things. ... (about which sorting algorithm is used) ...       size of the list to be sorted. ...
    (comp.programming)
  • Re: Value of inheritance in Object-oriented programming
    ... That is why when you want to get serious about time complexity in ... Turing machine transitions that it requires. ... When people count the time taken by a sorting algorithm in terms of ... effectively the only operation a sorting algorithm performs. ...
    (rec.games.roguelike.development)
  • Re: Static version of bignum library
    ... > a boundable maximum on the amount of memory used? ... what you have to do is analyze the needs of the algorithm. ... a certain easily estimated amount that you can preallocate. ... much storage will always be enough for the intermediate ...
    (comp.programming)