Optimality Analysis II
Making mathematical arguments usually involves assumptions about how the problem will be solved.
Invalidating the assumptions invalidates the lower bound.
Sorting an array of numbers requires at least ?(n) time, because it would take that much time to rearrange a list that was rotated one element out of position.