Why is the constant always dropped from big O analysis?

by

There’s a distinction between “are these constants meaningful or relevant?” and “does big-O notation care about them?” The answer to that second question is “no,” while the answer to that first question is “absolutely!”

Big-O notation doesn’t care about constants because big-O notation only describes the long-term growth rate of functions, rather than their absolute magnitudes. Multiplying a function by a constant only influences its growth rate by a constant amount, so linear functions still grow linearly, logarithmic functions still grow logarithmically, exponential functions still grow exponentially, etc. Since these categories aren’t affected by constants, it doesn’t matter that we drop the constants.

That said, those constants are absolutely significant! A function whose runtime is 10100n will be way slower than a function whose runtime is just n. A function whose runtime is n2 / 2 will be faster than a function whose runtime is just n2. The fact that the first two functions are both O(n) and the second two are O(n2) doesn’t change the fact that they don’t run in the same amount of time, since that’s not what big-O notation is designed for. O notation is good for determining whether in the long term one function will be bigger than another. Even though 10100n is a colossally huge value for any n > 0, that function is O(n) and so for large enough n eventually it will beat the function whose runtime is n2 / 2 because that function is O(n2).

In summary – since big-O only talks about relative classes of growth rates, it ignores the constant factor. However, those constants are absolutely significant; they just aren’t relevant to an asymptotic analysis.

Hope this helps!

More Related Contents:

  1. complexity in terms of big O
  2. time complexity of recursion function
  3. Big O, how do you calculate/approximate it?
  4. What does O(log n) mean exactly?
  5. Constant Amortized Time
  6. What exactly does big Ө notation represent?
  7. Can hash tables really be O(1)?
  8. Is log(n!) = Θ(n·log(n))?
  9. Difference between Big-O and Little-O Notation
  10. How can building a heap be O(n) time complexity?
  11. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  12. Big-O for Eight Year Olds? [duplicate]
  13. Which algorithm is faster O(N) or O(2N)?
  14. What would cause an algorithm to have O(log log n) complexity?
  15. Quick sort Worst case
  16. What is Constant Amortized Time?
  17. Computing set intersection in linear time?
  18. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  19. Painter puzzle – estimation
  20. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  21. What is amortized analysis of algorithms? [closed]
  22. Quicksort superiority over Heap Sort
  23. Why do we ignore co-efficients in Big O notation?
  24. Big O when adding together different routines
  25. Painter puzzle – algorithmic estimation from first principles
  26. Time Complexity of two for loops [duplicate]
  27. Difference between average case and amortized analysis
  28. Print the biggest K elements in a given heap in O(K*log(K))?
  29. Difference between Big-Theta and Big O notation in simple language
  30. Why is bubble sort O(n^2)?

Leave a Comment