3

I understand the formal definition of Big-O: $f(n)$ is $O(g(n))$ if there exist constants $N$ and $c$ such that for $n>N$ we have that $f(n) \leq c\cdot g(n)$. However, the problem is that, by this definition, $2n+1$ is $O(n^2)$ even though it is more precise to say that it is $O(n)$.

So, to resolve this, is it possible to modify the definition as such: $f(n)$ is precisely $O(g(n))$ if there exist $N$ and $k$ such that $f(n) \leq k\cdot g(n)$, and $f(n) \geq k^{-1}g(n)$, for $n>N$? Are there any possible issues with this definition?

Hossmeister
  • 817
  • 4
    You are (re-)discovering the Theta notation. Congrats! https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations – Did Jun 14 '18 at 22:32
  • 2
    @Did According with the article you cite, theta notation suppose the existence of two constats $k_1$ and $k_2$. The OP asks for using only one constant. I'm not sure both ways are the same. – Dog_69 Jun 14 '18 at 22:47
  • You are correct, big O notation only specifies an upper bound. As was commented, the tight bound you are looking for is big theta. The problem with your new big O definition is that is not what big O means. – BDN Jun 14 '18 at 23:10
  • @Dog_69 The existence of a finite upper bound $k_2$ and of a positive lower bound $k_1$ is strictly equivalent to the existence of a single bound $k\geqslant1$ used as $k$ for the upper bound and as $1/k$ for the lower bound. Thus, indeed, "both ways are the same". – Did Jun 15 '18 at 12:03

1 Answers1

2

Big-O notation lets you provide a loose upper bound for the behaviour of the function. It makes it easier to prove results quickly, and it also lets you group functions together and even provide simple demarcations between groups of functions.

This is what lets you do things like note the divide between polynomially-bounded functions (i.e. ones that are $O(x^n)$ for some $n \in \mathbb{N}$) and those that aren't.

And often, that's all you need. You're not trying to put strict asymptotic bounds on the function, you're just trying to get enough of an idea of its behaviour to work with in some fashion. And sometimes, trying to get a stricter bound is actually a lot of work, which will sometimes not be worth the effort.

ConMan
  • 24,300
  • The pertinence of the views expressed in the third paragraph is of course quite domain dependent. – Did Jun 15 '18 at 12:04
  • Situation-dependent, even. I wasn't trying to suggest that you never need theta notation, just that there are circumstances where the weaker bound is sufficient and that's when you can use big-O. – ConMan Jun 17 '18 at 23:27