patternMinor
Finding constants C and k for big-O of fraction of polynomials
Viewed 0 times
polynomialsbigforfindingandfractionconstants
Problem
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.
$$
|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.
Solution
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.)
$$ \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.)
Context
StackExchange Computer Science Q#22137, answer score: 6
Revisions (0)
No revisions yet.