Ohs, Omegas, or Thetas
Exercise 1.14
The following sentences refer to the insertion sort algorithm and the X’s hide an occurrence of O, \Omega, or \Theta.
For each of the sentences, indicate which options for X \in \{O, \Omega, \Theta\} make the statement true, which options make the statement false, and justify your answers:
The worst case is X(n^2).
The worst case is X(n).
The best case is X(n^2).
The best case is X(n).
For every probability distribution, the average case is X(n^2).
For every probability distribution, the average case is X(n).