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?

• You are (re-)discovering the Theta notation. Congrats! en.wikipedia.org/wiki/… – Did Jun 14 '18 at 22:32
• @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

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.