Quicksort Analysis
lOverall steps = cn x
number of levels.
lO(log(n)) levels in optimistic
case.
lO(n) levels in pessimistic
case.
lOverall O(n2).
lThe average
case can be shown to be O(n log(n)) based on a probabilistic
argument, assuming the data are initially
randomly distributed.