From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Theorem 3.1
For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

The worst case run time complexity of insertion sort is $O(n^2)$. However in case of sorted array the running time of the algorithm is $\Omega(n)$.

Don't these two things contradict with Theorem 3.1 when we say that run time complexity of Insertion sort in worst case is $\Theta(n^2)$.
Not sure if I am trying two mix different concepts; please help me in either case.

  • 1
    $\begingroup$ "Worst-case" refers to, well - as the name says, the "worst case". A presorted array is for insertion sort the best case. $\endgroup$
    – john_leo
    Aug 5, 2015 at 10:10
  • $\begingroup$ @john_leo Not much clear with your words. I understand the concept of Worst-case and best case. My question points toward the verification of theorem using insertion sort. $\endgroup$
    – Prateek
    Aug 5, 2015 at 10:18
  • $\begingroup$ But @john_leo pinpointed your problem quite accurately. The worst-case runtime is both in $O(n^2)$ and in $\Omega(n^2)$, ergo in $\Theta(n^2)$. The best-case runtime is in both $O(n)$ and $\Omega(n)$, ergo in $\Theta(n)$. This issue has been discussed at length in our reference question. $\endgroup$
    – Raphael
    Aug 5, 2015 at 10:21
  • $\begingroup$ when the input is in decreasing order the number of inversions (that is elements swapping their positions) will be $O(n^2)$. $\endgroup$ Aug 5, 2015 at 10:22