O(n log n) vs O(n) — practical differences in time complexity

The main purpose of the Big-O notation is to let you do the estimates like the ones you did in your post, and decide for yourself if spending your effort coding a typically more advanced algorithm is worth the additional CPU cycles that you are going to buy with that code improvement. Depending on the circumstances, you may get a different answer, even when your data set is relatively small:

  • If you are running on a mobile device, and the algorithm represents a significant portion of the execution time, cutting down the use of CPU translates into extending the battery life
  • If you are running in an all-or-nothing competitive environment, such as a high-frequency trading system, a micro-optimization may differentiate between making money and losing money
  • When your profiling shows that the algorithm in question dominates the execution time in a server environment, switching to a faster algorithm may improve performance for all your clients.

Another thing the Big-O notation hides is the constant multiplication factor. For example, Quick Select has very reasonable multiplier, making the time savings from employing it on extremely large data sets well worth the trouble of implementing it.

Another thing that you need to keep in mind is the space complexity. Very often, algorithms with O(N*Log N) time complexity would have an O(Log N) space complexity. This may present a problem for extremely large data sets, for example when a recursive function runs on a system with a limited stack capacity.

Related Posts:

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

Leave a Comment