in reply to An informal introduction to O(N) notation
The infamous Bubble Sort is O(N^{2}).
So is quicksort, in the worst case. :) Mergesort and heapsort are both O(N log N) in the worst case.
Most of the time, there's no difference in asymptotic order between the average and worstcase inputs, but every once in a while, something (like quicksort) comes along and bites you on the ass on certain inputs. Quicksort expects its input to be mostly random; ordered input will mess it up. (Think about building a binary tree from ordered input: you'll get a linear list, which is O(N) nodes deep, not a nice bushy tree, which would be O(log N) nodes deep.) Something to think about when building divide and conquer algorithms.

F
o
x
t
r
o
t
U
n
i
f
o
r
m
Found a typo in this node? /msg me
The hell with paco, vote for Erudil!
