Is there a clever shortcut to showing that this function is in O(N^2)?

Question

This problem is from Discrete Mathematics and its Applications

I am currently working on 2a.

I am trying to apply an example the book gave earlier

Is there some similar clever trick I can apply to 2a to shorten the math I would have to do? Here is the work I have so far

I prefer not to go through the quadratic equation solver http://www.mathsisfun.com/quadratic-equation-solver.html and getting some floating point value but i can't find something like x > 7 for 17x + 11

Answer 1

You want to show that $17x+11$ is $O(x^2)$.

This is easiest if you don't start with deciding on a constant factor, but instead start by finding a suitable lower bound for the inequality.

For example, suppose $x>11$. Then

$$ \tag{*} 17x+11 < 17x+x < 18x $$

Hmm, this would be less than $x^2$ if only $x>18$. But since $18>11$, all of (*) is still true for $x>18$, so we can change our mind and say that for $x>18$ we have

$$ 17x+11 < 17x+x < 18 x < x^2 $$

Thus we can conclude that $17x+11=O(x^2)$ because $17x+11\le 1\cdot x^2$ for all $x>18$. This is not the "best possible" constants, but in order to prove the result it is enough to find a set that works.

Answer 2

The function $h\colon x \in [1,\infty) \mapsto \frac{f(x)}{x^2}$ goes to $0$, as $$\frac{f(x)}{x^2} = \frac{17x+11}{x^2} \xrightarrow[x\to\infty]{} 0.$$ Having a limit at $\infty$ (and by continuity) $h$ is bounded, and in particular there exists $C > 0$ such that, for all $x \geq 1$, $\frac{f(x)}{x^2} \geq C$. Equivalently, $f(x) \leq C x^2$ for all $x \geq 1$, proving that $f(x)=O(x^2)$.

Answer 3

First note that the choices of $C$ and $k$ witnesses are not unique.

The answer to the first problem is yes since $$ 17x+11\leq 17x+x = 18x\leq 18x^2 $$ for all $x>11$. The witnesses are $C=18$ and $k=11$.