algorithm-complexity – Definition "Little-O" notation (Small O)

Question:

I would like to understand a little better about Little-O Notation, it's for academic purposes, but I haven't found enough content or a little more "clear" form for understanding. I'm a little lost about it due to lack of study material.

Answer:

Note: I will use the letter o (lowercase) for little-o; and O (capital) for big-O


We say that a function f is contained in o(g) if for all x is true that f(x) < g(x) .

We say that a function f is contained in O(g) if for all x is true that f(x) <= g(x) .

For example, consider the function f(x) = x^2

  • f is in o(x^3) and in O(x^3)
  • f is not o(x^2) nor in O(x)

Note that if f is contained in o(g) then it will necessarily be in O(g) well.

Scroll to Top