Now consider InsertionSort:

$($c$)$ Assuming Insert runs in constant time O$(1)$ for inputs of length n$,$ Show that InsertionSort has a runtime of O$($n $+$ log$2($n$!)).$

$($d$)$ Assuming Insert runs in linear time O$($n$)$ for inputs of length n$,$ Show that InsertionSort has a runtime of O$($n$^\{2\}$ log$2$ n$)$

$($e$)$ Write your own pseudocode for Insert that runs in linear time in the worst case.

$($f$)($graded on fair effort completeness$)$ Can you think of any way to make Insert run faster than

linear time? Why or why not?