Optimality Analysis I
To discover an optimal algorithm we need to find an upper and lower asymptotic bound for a problem.
An algorithm gives us an upper bound. The worst case for sorting cannot exceed ?(n2) because we have Insertion Sort that runs that fast.
Lower bounds require mathematical arguments.