Are there any O(1/n) algorithms?

by

This question isn’t as silly as it might seem to some. At least theoretically, something such as O(1/n) is completely sensible when we take the mathematical definition of the Big O notation:

Now you can easily substitute g(x) for 1/x … it’s obvious that the above definition still holds for some f.

For the purpose of estimating asymptotic run-time growth, this is less viable … a meaningful algorithm cannot get faster as the input grows. Sure, you can construct an arbitrary algorithm to fulfill this, e.g. the following one:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Clearly, this function spends less time as the input size grows … at least until some limit, enforced by the hardware (precision of the numbers, minimum of time that sleep can wait, time to process arguments etc.): this limit would then be a constant lower bound so in fact the above function still has runtime O(1).

But there are in fact real-world algorithms where the runtime can decrease (at least partially) when the input size increases. Note that these algorithms will not exhibit runtime behaviour below O(1), though. Still, they are interesting. For example, take the very simple text search algorithm by Horspool. Here, the expected runtime will decrease as the length of the search pattern increases (but increasing length of the haystack will once again increase runtime).

More Related Contents:

  1. What is a plain English explanation of “Big O” notation?
  2. Big O, how do you calculate/approximate it?
  3. Computational complexity of Fibonacci Sequence
  4. Constant Amortized Time
  5. Time complexity of nested for-loop
  6. Determining complexity for recursive functions (Big O notation)
  7. Is log(n!) = Θ(n·log(n))?
  8. How can building a heap be O(n) time complexity?
  9. Big-O for Eight Year Olds? [duplicate]
  10. Time complexity of python set operations?
  11. Is list::size() really O(n)?
  12. Python dictionary keys. “In” complexity
  13. What would cause an algorithm to have O(log log n) complexity?
  14. Is Big O(logn) log base e?
  15. Finding Big O of the Harmonic Series
  16. What is Constant Amortized Time?
  17. What is Turing Complete?
  18. What is the complexity of regular expression?
  19. multiset, map and hash map complexity
  20. What is Big O notation? Do you use it? [duplicate]
  21. Efficiently finding the intersection of a variable number of sets of strings
  22. What is the complexity of this simple piece of code?
  23. Why do we ignore co-efficients in Big O notation?
  24. Time Complexity of two for loops [duplicate]
  25. Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?
  26. Finding out the duplicate element in an array
  27. Prove that binary heap build max comparsion is (2N-2)
  28. Why is bubble sort O(n^2)?
  29. Example of O(n!)?
  30. What is referential transparency?

Leave a Comment