Big-O notation

[Paul Moore]

Erik Max Francis <max at alcyone.com> writes:

>> But these are not really 'algorithms'. Most algorithms are a lot
>> more complex even when reduced to it's essentials. I understand why
>> quicksort is better than bubblesort but I don't see an obvious way
>> to label quicksort O(??).
>
> But there is always some set of behaviors that are core to the
> algorithm, and that's what you look at as the number of elements goes to
> infinity.  Bubble sort is O(n^2), but quicksort is O(n ln n).

Just to clarify this point a bit, the measure usually used in sorting
is the number of swaps of two elements (or the number of comparisons -
these are usually equivalent in terms of O() calculations).

So, you look at bubblesort. Basically, each element gets compared
against each other - that's n * n comparisons, hence O(n**2).

But for quicksort you partition, and compare each element against the
partitioning element. That's n comparisons against log(n) partitioning
elements (each partitioning step halves the size of the chunks, so you
do this log2(n) times). So the complexity is O(n*log(n)).

Disclaimer: This is all *very* rough, and from memory as well. But I
hope it's enough that you get the idea.

Paul.
-- 
This signature intentionally left blank