I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the constants $C$ and $k$ in the definition of big-O $$ |f(x)| \leq C|g(x)|, x > k, $$ when the function $f(x)$ is a fraction of polynomials.

I have tried to concoct my own method, but I am unsure of its correctness. I was inspired by the easy method of finding $C$ and $k$ for a polynomial where for example we can show that $x^3+2x+3$ is $O(x^3)$ by $$ x^3+2x+3 \leq x^3+2x^3+3x^3 = 6x^3 $$ to find $C = 6$ and $k = 1$.

Now, for a fraction of polynomials I am unsure what to do with the denominator. My attempt at a general method is as follows. I would like to show that $\frac{x^4+x^2x1}{x^3+1}$ is $O(x)$. First I divide by the highest term in the denominator to get a $1$ in the denominator: $$ \frac{(x^4+x^2+1)/x^3}{(x^3+1)/x^3} = \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} $$ Now I argue, somewhat analogously to the previous example, that the fractions in the numerator must be less than (when x > 0) x, and since a smaller denominator makes the expression smaller, setting all the terms in denominator except the $1$ to $0$, I obtain the inequality $$ \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} \leq \frac{x+x+x}{1+0} = 3x $$ and I find $C = 3$ and $k = 1$.

Now my question is, does this homebrewed method actually work or is it complete nonsense? And if it is nonsense, does anybody know of another general method for finding $C$ and $k$ in instances like this?

Note that I need to find the constants $C$ and $k$, not just show that a given function is big-O of some other function, and the students have had no course in calculus, so I can use no concepts from there, such as limits.

  • 2
    $\begingroup$ By the way, your "fractions of polynomials" are known as rational functions. $\endgroup$ Commented Feb 28, 2014 at 22:19

3 Answers 3


Remember that $O(-)$ is just an upper bound.

Given a rational function $p(x)/q(x)$, you already know how to find $c$, $k$ and $x_0$ such that $|p(x)|\leq c|x^k|$ for $x>x_0$. By similar arguments, you can show that $|q(x)|\ge 1$ for all $x$ greater than some $x_1$. Therefore, for all $x>\max\{x_0,x_1\}$, we have $|p(x)/q(x)| \leq |p(x)| \leq c|x^k|$ so $p(x)/q(x) = O(x^k)$.

  • $\begingroup$ Of course, this bound is not particularly tight in general... $\endgroup$ Commented Mar 1, 2014 at 1:52
  • $\begingroup$ Agreed but the question doesn't ask for tight bounds: it just asks for a method of finding the two constants. And it's not usually worth spending a whole lot of time quantifying exactly what "for large enough $n$" means. Normally, it's sufficient to exhibit some value of the constants that works and optimizing them doesn't gain you anything. $\endgroup$ Commented Mar 1, 2014 at 10:50
  • $\begingroup$ This is a very simple and convincing argument, I'll try to use it. Thanks! $\endgroup$
    – mrp
    Commented Mar 2, 2014 at 8:03

It works if the denominator doesn't have negative coefficients. Consider, however, $$ \frac{x}{x-1}. $$ As $x$ tends to infinity, this is $O(1)$. However, your method would give $$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$ which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case it is zero, but for an example like $$ \frac{x}{x-2} = \frac{1}{1-\tfrac{2}{x}} \leq \frac{1}{-1} = -1, $$ the inequality is in fact wrong.

Often when considering $O(f(x))$, we assume that $f(x)$ is always positive. But sometimes it isn't, and then the assumption that we're making is that $f(x)$ is eventually positive. This is not usually explained when big O notation is defined, but it's the reason behind the extra quantifier "for large enough $x$" which appears in the full definition of big O; this quantifier is only needed when $f(x)$ is not always positive but only eventually positive.

The way to fix the argument is now clear. If $f(x)$ is eventually positive, then take some $y$ such that $f(x) > 0$ for all $y \geq x$, and now apply the method. For example, if $f(x) = x/(x-1)$ then any $y > 1$ would do, say $y = 2$. In that case we have $$ f(x) = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-\frac{1}{2}} = 2 $$ for $x \geq 2$.

More generally, suppose that $f(x) = C p(x)/q(x)$, where $p,q$ are monic polynomials (leading coefficient is $1$) and are eventually positive, and $C > 0$. Then for all $\epsilon > 0$ there is $y$ such that for all $x \geq y$, $$ (C-\epsilon) x^{\deg p - \deg q} < f(x) < (C+\epsilon) x^{\deg p - \deg q}. $$ (Exercise.)


Compare the definition of the Bachman-Landau notations to the definition of a limit when $n \to \infty$, the relation between them is enough for cars like this.

  • $\begingroup$ From the question: "the students have had no course in calculus, so I can use no concepts from there, such as limits." $\endgroup$ Commented Mar 1, 2014 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.