Contradiction between best-case running time of insertion sort and $n\log n$ lower bound?

Question

If the best case for Insertion sort & bubble sort is $O(n)$ then how is lower bound for any comparison sort is $\Omega(n\log n)$? I mean, $O(n)$ is obviously smaller than $\Omega(nlogn)$. What am I missing here?

Answer 1

The lower bound of $\Omega(n \log(n))$ is a lower bound for the worst-case behavior of a sorting method. Both insertion sort and bubble sort have $O(n^2)$ worst-case complexity.

Answer 2

Given an algorithm $A$, we often consider its worst-case time complexity $T(A)$ over all possible inputs $I$: $$T(A) = \max_{I} T(A,I)$$ where, $T(A,I)$ is the time for the algorithm $A$ executed on this particular input $I$.

For a problem $P$, we may have several algorithms $A$ for it. The time complexity (or lower bound) of a problem $T(P)$ is defined with respect to its best algorithms.

$$T(P) = \min_{A} T(A) = \min_{A} \max_{I} T(A,I)$$

---

For sorting problem, its lower bound (comparison-based) is $\Omega(n \lg n)$. Both $\texttt{Insertion-Sort}$ and $\texttt{Bubble-Sort}$ have worst-case time complexity of $\Theta(n^2)$, and thus do not match the lower bound. In contrary, both $\texttt{Merge-Sort}$ and $\texttt{Heap-Sort}$ have worst-case time complexity of $\Theta(n \lg n)$, matching the lower bound.