Which is better: O(n log n) or O(n^2)

Just ask wolframalpha if you have doubts.

In this case, it says

     n log(n)
lim --------- = 0
       n^2

Or you can also calculate the limit yourself:

     n log(n)        log(n)   (Hôpital)       1/n          1
lim --------- = lim --------      =     lim ------- = lim --- = 0
       n^2             n                       1           n

That means n^2 grows faster, so n log(n) is smaller (better), when n is high enough.

Related Posts:

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