3
$\begingroup$

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?

$\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
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.