Problem Detail: 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^2×1}{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.
Asked By : mrp
Answered By : David Richerby
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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22137
