Definition Notation "Little-O" ( Small O)

Asked

Viewed 474 times

3

I would like to understand a little better about Little-O Notation, it is for academic purposes, however I have not found enough content or in a somewhat "clear" way, for understanding. I’m a little lost in relation due to lack of study material.

  • 1

    Hello @Italo, welcome to Stackoverflow PT. Enjoy doing the Tour to better understand the operation of the site.

1 answer

1

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


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

We say a function f is contained in O(g) if for all x it 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 nay is o(x^2) nor in O(x)

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

Browser other questions tagged

You are not signed in. Login or sign up in order to post.