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(n2)or O(n3), can we say that the complexity is O(n2) or O(n3)? Then in this case counting sort is not a wise approach and we can use merge sort. Am I right?
是的，你在所有方面都是完全正确的。
Furthermore, we can make stronger statements: when k=O(n2) or O(n3), we can say that the complexity of the counting sort is Θ(n2) or Θ(n3).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
