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?
$\begingroup$
$\endgroup$
-
4$\begingroup$ The lower bound of $\Omega(n\log(n))$ is a lower bound for the worst-case behavior of a sorting method. $\endgroup$ – user340082710 Jan 24 '15 at 20:19
$\begingroup$
$\endgroup$
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.
answered Jan 25 '15 at 2:05
$\begingroup$
$\endgroup$
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.
