0

The definition of little-o asymptotic notation says "f(x) is ο(g(x)), if for any constant c > 0, there exists an n0 such that 0 ≤ f(n) < c*g(n)."

With this definition, we know, any linear function of x is o(x^2) and o(x^n) for any n > 1.

Can we also say f(x) = 2x + 1 is o(-5x^2 +2), because for some values of x near 0, (2x+1)<(-5cx^2 +2), where c is any positive constant? Graph

If answer to the above question is yes, then, another question I get -

say g1(x) = (-5x^2 + 2), g2(x) = -5x^2. Here g1(x) and g2(x) are of same order. Let f(x) = (2x+1). Since f(x) = o(g1(x)), so f(x) = o(g2(x))??

If this is also true, then the graph I added above shows that g2(x) < f(x) for all values of x. So f(x) is not g2(x), which is a contradiction!!

If f(x) = o(g2(x)), then the definition of little-o has to be modified as |f(x)| and |g(x)| in place of f(x) and g(x).

"f(x) is ο(g(x)), if for any constant c > 0, there exists an n0 such that 0 ≤ |f(n)| < c*|g(n)|."

Please let me know your thoughts.

Monalisha Bhowmik
  • 131
  • 6

1 Answers1

2

Actually, your definition is not complete, for little o we have:

Definition : Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is ο(g(n)) (or f(n) Ε ο(g(n))) if for any real constant c > 0, there exists an integer constant n0 ≥ 1 such that 0 ≤ f(n) < c*g(n); for all n greater than n0.

also, you can see more in this answer

amirhe
  • 2,186
  • 1
  • 13
  • 27
  • If the definition should contain positive integer to positive real numbers mapping for both f and g, then fine. However, in this link given, positive is not mentioned. Somewhere it is given, somewhere else not given, it's confusing. Can not g(n) have negative values for positive inputs? – Monalisha Bhowmik Dec 08 '20 at 14:26
  • 1
    I guess, this gonna be an in-minded assumption, cause all of these definitions are defined for complexity theory which is targeting algorithms runtimes and negative run time simply doesn't make sense. Looking pure by mathematic vision, all upper bound of a function can be a little o, by convention Big O is represented at the lowest upper bound of the function (for numbers bigger than n0). – amirhe Dec 08 '20 at 20:20
  • also for little o, we must have: 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. this will not happen for relatively small k near 0, so f is not o(g) – amirhe Dec 08 '20 at 20:21