Over Estimation of big O

It is likely that we can over estimate the big O and get stuck with the upper bound when in fact the average case is more important.

Dynamic array example. Upper bound is n log n but average case is n.