Question $5$

The counting sort has $\backslash ($ O$($n$+$k$)\backslash )$ time complexity. Give asymptotic lower and upper bounds for $\backslash ($ k $\backslash )$ in terms of $\backslash ($ n $\backslash ),$ such that the counting sort is not linear in $\backslash ($ n $\backslash )$ but still better than Merge Sort. In other words, consider for which lower bound for $\backslash ($ k $\backslash )$ the counting sort becomes super$-$linear $($more expensive than linear$),$ and for which upper bound for $\backslash ($ k $\backslash )$ the counting sort is still asymptotically more efficient than the MergeSort. In order to get full credit, we should not be able to improve your bounds.

Hint: You need to use appropriate asymptotic notation and give the lower and the upper bounds.