title: The time complexity of counting sort
body: <p>I am taking an algorithms course and there I saw that the time complexity of counting sort is O(n+k) where k is the range of numbers and n is the input size. My question is, when the difference between k and n is too much, such as when k=O(n<sup>2</sup>)or O(n<sup>3</sup>), can we say that the complexity is O(n<sup>2</sup>) or O(n<sup>3</sup>)? Then in this case counting sort is not a wise approach and we can use merge sort. Am I right? </p>