[algorithm] Difference between Big-O and Little-O Notation

f ? O(g) says, essentially

For at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) <= k g(x) holds for all x > a.

Note that O(g) is the set of all functions for which this condition holds.

f ? o(g) says, essentially

For every choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) < k g(x) holds for all x > a.

Once again, note that o(g) is a set.

In Big-O, it is only necessary that you find a particular multiplier k for which the inequality holds beyond some minimum x.

In Little-o, it must be that there is a minimum x after which the inequality holds no matter how small you make k, as long as it is not negative or zero.

These both describe upper bounds, although somewhat counter-intuitively, Little-o is the stronger statement. There is a much larger gap between the growth rates of f and g if f ? o(g) than if f ? O(g).

One illustration of the disparity is this: f ? O(f) is true, but f ? o(f) is false. Therefore, Big-O can be read as "f ? O(g) means that f's asymptotic growth is no faster than g's", whereas "f ? o(g) means that f's asymptotic growth is strictly slower than g's". It's like <= versus <.

More specifically, if the value of g(x) is a constant multiple of the value of f(x), then f ? O(g) is true. This is why you can drop constants when working with big-O notation.

However, for f ? o(g) to be true, then g must include a higher power of x in its formula, and so the relative separation between f(x) and g(x) must actually get larger as x gets larger.

To use purely math examples (rather than referring to algorithms):

The following are true for Big-O, but would not be true if you used little-o:

  • x² ? O(x²)
  • x² ? O(x² + x)
  • x² ? O(200 * x²)

The following are true for little-o:

  • x² ? o(x³)
  • x² ? o(x!)
  • ln(x) ? o(x)

Note that if f ? o(g), this implies f ? O(g). e.g. x² ? o(x³) so it is also true that x² ? O(x³), (again, think of O as <= and o as <)

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to big-o

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) What exactly does big ? notation represent? How to merge two sorted arrays into a sorted array? Time complexity of Euclid's Algorithm Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)? Append an object to a list in R in amortized constant time, O(1)? What does O(log n) mean exactly? Is log(n!) = T(n·log(n))? Difference between Big-O and Little-O Notation

Examples related to asymptotic-complexity

Difference between Big-O and Little-O Notation

Examples related to little-o

Difference between Big-O and Little-O Notation