# 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)$.
• 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. – Raphael Aug 5 '15 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)$. – Coffee_lover Aug 5 '15 at 10:22