Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?

It means that the thing in question (usually running time) scales in a manner that is consistent with the logarithm of its input size.

Big-O notation doesn’t mean an exact equation, but rather a bound. For instance, the output of the following functions is all O(n):

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

Because as you increase x, their outputs all increase linearly – if there’s a 6:1 ratio between f(n) and g(n), there will also be approximately a 6:1 ratio between f(10*n) and g(10*n) and so on.

As for whether O(n) or O(log n) is better, consider: if n = 1000, then log n = 3 (for log-base-10). Which would you rather have your algorithm take to run: 1000 seconds, or 3 seconds?

Related Posts:

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