Message-ID: <34C8D694.2C81@pobox.oleane.com>
Date: Fri, 23 Jan 1998 18:42:44 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: Charles Krug <charles AT pentek DOT com>
CC: djgpp AT delorie DOT com
Subject: Re: The meaning of O(n)...
References: <Pine DOT GSO DOT 3 DOT 96 DOT 980120190605 DOT 19121B-100000 AT bert DOT eecs DOT uic DOT edu> <34C8B7D1 DOT A19B36EA AT pentek DOT com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Precedence: bulk

Charles Krug wrote:
> 
> If you look at quicksort, you see log(n)
> outer loops, each containing (n-1) inner loops, giving a complexity of
> log(n)(n-1) or nlog(n) - log(n).  Which has a complexity of nlog(n).
> 

Nitpicking a little here: Quicksort is not an nlog(n) algorithm, but an 
n^2 one, in its worst case. However, this worst case is very rare (for 
large values of n), and a correct implementation may make it very 
unlikely in all practical cases. 

There are nlog(n) sorting algorithms though, one of them being Heapsort. 
But Quicksort happens to be faster on average (though its "nominal 
complexity" is higher).

This is an important point when choosing an algorithm. An nlog(n) 
algorithm transforms some data of length n in Knlog(n) steps, K being a 
constant. The value of K may have a drastic effect on the actual speed of 
the program. In fact, in several cases, an o(nlog(n)) algorithm with low 
K may be preferable (for some values of n) to an o(n) one with a higher 
constant (as an example, the Fast Fourier Transform, an o(nlogn) 
algorithm, is usually faster, for standard values of n, the Fast Wavelet 
Transform algorithm, which is o(n)).

Francois