Is there an O(n) integer sorting algorithm?

Yes, Radix Sort and Counting Sort are O(N). They are NOT comparison-based sorts, which have been proven to have Ω(N log N) lower bound.

To be precise, Radix Sort is O(kN), where k is the number of digits in the values to be sorted. Counting Sort is O(N + k), where k is the range of the numbers to be sorted.

There are specific applications where k is small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.

Related Posts:

  1. What is stability in sorting algorithms and why is it important?
  2. What is the difference between bucket sort and radix sort?
  3. What does O(log n) mean exactly?
  4. how to calculate binary search complexity
  5. What does O(log n) mean exactly?
  6. Quicksort with Python
  7. how to implement quick sort algorithm in C++
  8. Why is the time complexity of both DFS and BFS O( V + E )
  9. Breadth First Search time complexity analysis
  10. Time Complexity of the Kruskal Algorithm?
  11. Quick Sort Vs Merge Sort
  12. Insertion Sort vs. Selection Sort
  13. When will the worst case of Merge Sort occur?
  14. O(n log n) vs O(n) — practical differences in time complexity
  15. Trying to understand max heapify
  16. Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
  17. What is tail call optimization?
  18. Quicksort vs heapsort
  19. Best case time complexity for selection sort
  20. Trie complexity and searching
  21. Is complexity O(log(n)) equivalent to O(sqrt(n))?
  22. Exactly how many comparisons does merge sort make?
  23. Merge sort time and space complexity
  24. How to calculate time complexity of backtracking algorithm?
  25. Median of Medians in Java
  26. Hash table runtime complexity (insert, search and delete)
  27. Which is better: O(n log n) or O(n^2)
  28. Quickselect time complexity explained
  29. Difference between Big-O and Little-O Notation
  30. Why is O(n) better than O( nlog(n) )?
  31. An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
  32. Create your own MD5 collisions
  33. Finding all possible combinations of numbers to reach a given sum
  34. Sorting an array in C?
  35. About bubble sort vs merge sort
  36. In a triangulated isometric grid, what triangle is a given point in?
  37. What is tail recursion?
  38. How do I check if an array includes a value in JavaScript?
  39. What is a loop invariant?
  40. What is a loop invariant?
  41. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
  42. What is Sliding Window Algorithm? Examples?
  43. What is the difference between tree depth and height?
  44. Python: maximum recursion depth exceeded while calling a Python object
  45. Understanding Time complexity calculation for Dijkstra Algorithm
  46. Time complexity of a Priority Queue in C++
  47. Counting the sum of every nodes’ neighbors’ degrees?
  48. Difference and advantages between dijkstra & A star
  49. Best Case for Bubble Sort
  50. How to find the kth smallest element in the union of two sorted arrays?
  51. Big O, how do you calculate/approximate it?
  52. Will Arrays.sort() increase time complexity and space time complexity?
  53. Performing Breadth First Search recursively
  54. Is Quicksort in-place or not?
  55. longest increasing subsequence(O(nlogn))
  56. When should I use Kruskal as opposed to Prim (and vice versa)?
  57. Python Weighted Random [duplicate]
  58. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  59. What’s a good algorithm to generate a maze?
  60. Intuition for perceptron weight update rule
  61. Easy: Solve T(n)=T(n-1)+n by Iteration Method
  62. PacMan: what kinds of heuristics are mainly used?
  63. Big-oh vs big-theta
  64. What is a good Hash Function?
  65. Looking for algorithm finding euler path
  66. What does this definition of contiguous subsequences mean?
  67. Is log(n!) = Θ(n·log(n))?
  68. How to find maximum spanning tree?
  69. How to calculate big-theta
  70. What is the time complexity of while loops?
  71. Intuitive explanation for why QuickSort is n log n?
  72. Calculate distance between two latitude-longitude points? (Haversine formula)
  73. Shuffle a deck of cards in Java
  74. When should we use Radix sort?
  75. What is a loop invariant?
  76. Why does heap sort have a space complexity of O(1)?
  77. What is O(log* N)?
  78. What is the proper equivalent of “while(true)” in plain C?
  79. Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
  80. Asymptotic Notation – does n (log n) (log n) simplify?
  81. What is the big-O of the function (log n)^k
  82. How to calculate an angle from three points?
  83. How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
  84. how to write a recurrence relation for a given piece of code
  85. How to sort in-place using the merge sort algorithm?
  86. Why is merge sort worst case run time O (n log n)?
  87. Why is merge sort worst case run time O (n log n)?
  88. What is the time and space complexity of a breadth first and depth first tree traversal?
  89. A tool for calculating the big-O time complexity of Java code? [closed]
  90. Image Segmentation using Mean Shift explained
  91. Finding the median of an unsorted array
  92. Difference between Big-Theta and Big O notation in simple language
  93. How are the following functions O(N^3)?
  94. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  95. Are there any real O(n^n) algorithms?
  96. Is Dijkstra’s algorithm for directed or undirected graphs?
  97. How to determine if a point is in a 2D triangle?
  98. Modular multiplicative inverse function in Python
  99. Minesweeper solving algorithm
  100. Best way to randomize an array with .NET

Leave a Comment