1

Whether the little-o is tight upper bound or strict upper bound?

Correct the answer below if wrong,

g(x) is an upper bound for f(x) that is not asymptotically tight. There is a much larger gap between the growth rates of f and g if f ∈ o(g) than if f ∈ O(g).

Big-O is to little-o as ≤ is to <. big-O is an inclusive upper bound, while little-o is a strict upper bound.

Isn't it enough to guarantee a strict upper bound?

danglingpointer
  • 4,708
  • 3
  • 24
  • 42
Iyyara
  • 11
  • 2

1 Answers1

0

Your intuition looks correct, but I am not sure about your use of terms.

From Wikipedia: big-O vs little-o

In this way, little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g (for instance g itself is not, unless it is identically zero near ∞).

Another useful quote:

the relation f(x) = o(g(x)) is equivalent to
lim(f(x)/g(x)) = 0 (when x -> ∞)
vs
the relation f(x) = O(g(x)) is equivalent to
lim(f(x)/g(x)) < ∞ (when x -> ∞)

Ayrat
  • 1,221
  • 1
  • 18
  • 36