Time complexity

Question

Consider the following statements

 The best case complexity of insertion sort is $\Omega \left ( n^{2} \right )$

The best case complexity of insertion sort is $O\left ( n \right )$

Which one true?

Comments

how can be both are true:

1st say >  n²

2nd say < n

https://gateoverflow.in/128680/derive-the-best-and-worst-case-complexity-of-insertion-sort

https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/analysis-of-insertion-sort

---

yes  tnks

---

if it is told $\Omega \left ( n \right )$

then it will be correct?

because $\Omega$ means $\geq$

right?

Answer 1

2nd option is true!

Explanation :-

Best Case O(n) - If the input is in ascending order then we need only n comparisons for n elements and no movements

Worst case O(n²) - if input is in descending or other than ascending order. Because if input is in Desc order we need to do n comparisons and at max (n-1) movements.

Comments

i guess both are true because Big Omega will be in the form of >=c

and Big Oh is <=c

Answer 2

Insertion sort Best case is O(n).

which can be written as

Ω(n^2) because bound will be >=c, here c is 'n'.

As far as I know this is correct. If its wrong then correct me.

Comments

Big O is the tightest upper bound and Omega is tightest lower bound!
In Insertion sort If best case in O(n) then how come its tightest lower bound is of (n^2).

Hence option 1 is incorrect.

---

got it. thank u :)