# Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

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.

• "Worst-case" refers to, well - as the name says, the "worst case". A presorted array is for insertion sort the best case. Aug 5, 2015 at 10:10
• @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. Aug 5, 2015 at 10:18
• 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. Aug 5, 2015 at 10:21
• when the input is in decreasing order the number of inversions (that is elements swapping their positions) will be $O(n^2)$. Aug 5, 2015 at 10:22