Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329

f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant

f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink

Big O basically drops constants

O(2n+1) = O(2n) = O(n)

o(2n+1) > o(2n) > o(n)

Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"

If f is O(g) and o(h) then

  Lim f/g -> C a constant

  Lim f/h -> 0

Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.

https://stackoverflow.com/questions/1364444/difference-betwe...