Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?

by

There can be many reasons to prefer an algorithm with higher big O time complexity over the lower one:

  • most of the time, lower big-O complexity is harder to achieve and requires skilled implementation, a lot of knowledge and a lot of testing.
  • big-O hides the details about a constant: algorithm that performs in 10^5 is better from big-O point of view than 1/10^5 * log(n) (O(1) vs O(log(n)), but for most reasonable n the first one will perform better. For example the best complexity for matrix multiplication is O(n^2.373) but the constant is so high that no (to my knowledge) computational libraries use it.
  • big-O makes sense when you calculate over something big. If you need to sort array of three numbers, it matters really little whether you use O(n*log(n)) or O(n^2) algorithm.
  • sometimes the advantage of the lowercase time complexity can be really negligible. For example there is a data structure tango tree which gives a O(log log N) time complexity to find an item, but there is also a binary tree which finds the same in O(log n). Even for huge numbers of n = 10^20 the difference is negligible.
  • time complexity is not everything. Imagine an algorithm that runs in O(n^2) and requires O(n^2) memory. It might be preferable over O(n^3) time and O(1) space when the n is not really big. The problem is that you can wait for a long time, but highly doubt you can find a RAM big enough to use it with your algorithm
  • parallelization is a good feature in our distributed world. There are algorithms that are easily parallelizable, and there are some that do not parallelize at all. Sometimes it makes sense to run an algorithm on 1000 commodity machines with a higher complexity than using one machine with a slightly better complexity.
  • in some places (security) a complexity can be a requirement. No one wants to have a hash algorithm that can hash blazingly fast (because then other people can bruteforce you way faster)
  • although this is not related to switch of complexity, but some of the security functions should be written in a manner to prevent timing attack. They mostly stay in the same complexity class, but are modified in a way that it always takes worse case to do something. One example is comparing that strings are equal. In most applications it makes sense to break fast if the first bytes are different, but in security you will still wait for the very end to tell the bad news.
  • somebody patented the lower-complexity algorithm and it is more economical for a company to use higher complexity than to pay money.
  • some algorithms adapt well to particular situations. Insertion sort, for example, has an average time-complexity of O(n^2), worse than quicksort or mergesort, but as an online algorithm it can efficiently sort a list of values as they are received (as user input) where most other algorithms can only efficiently operate on a complete list of values.

More Related Contents:

  1. What is a plain English explanation of “Big O” notation?
  2. What does O(log n) mean exactly?
  3. Difference between Big-O and Little-O Notation
  4. Time complexity of Euclid’s Algorithm
  5. What would cause an algorithm to have O(log log n) complexity?
  6. What is pseudopolynomial time? How does it differ from polynomial time?
  7. What would cause an algorithm to have O(log n) complexity?
  8. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  9. Why do we ignore co-efficients in Big O notation?
  10. complexity in terms of big O
  11. Calculating Big O Notation for a algorithm [duplicate]
  12. O(3^n) exponential time complexity [closed]
  13. Big O, how do you calculate/approximate it?
  14. How can I find the time complexity of an algorithm?
  15. Can hash tables really be O(1)?
  16. Why is the constant always dropped from big O analysis?
  17. How can building a heap be O(n) time complexity?
  18. Is there an O(n) integer sorting algorithm?
  19. Which algorithm is faster O(N) or O(2N)?
  20. Hash table runtime complexity (insert, search and delete)
  21. What is Constant Amortized Time?
  22. how to calculate binary search complexity
  23. Argument for O(1) average-case complexity of heap insertion
  24. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  25. Why is the time complexity of both DFS and BFS O( V + E )
  26. Big O of JavaScript arrays
  27. Calculating phi(k) for 1
  28. Prove that binary heap build max comparsion is (2N-2)
  29. Why is bubble sort O(n^2)?
  30. Computational complexity of base conversion

Leave a Comment