Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
+1 Looks good to me. –  Patrick87 Feb 28 at 20:06
2  
By the way, your "fractions of polynomials" are known as rational functions. –  David Richerby Feb 28 at 22:19

3 Answers 3

up vote 3 down vote accepted

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)$.

share|improve this answer
    
Of course, this bound is not particularly tight in general... –  Yuval Filmus Mar 1 at 1:52
    
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. –  David Richerby Mar 1 at 10:50
    
This is a very simple and convincing argument, I'll try to use it. Thanks! –  mrp Mar 2 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.)

share|improve this answer

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.

share|improve this answer
    
From the question: "the students have had no course in calculus, so I can use no concepts from there, such as limits." –  David Richerby Mar 1 at 16:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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