in reply to An informal introduction to O(N) notation
The infamous Bubble Sort is O(N2).
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 worst-case 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.