Finding $k$, $C_1$, and $C_2$ when $f(x)$ is $Θ(g(x))$

Question

How can I find the constants $k$, $C_1$, and $C_2$ when I know that $f(x)$ is $Θ(g(x))$?

$f(x)=3x^2+x+1$ and $g(x)=3x^2$

I have that

$C_1g(x) \le f(x) \le C_2g(x)$

$C_1 \le \frac{f(x)}{g(x)} \le C_2$, but where do I go from here?

Answer 1

We can take any $C_1 \in (0,1]$ and any $C_2 \in (1,\infty)$.

We check the following:

• We have $$C_1\ 3x^2 \leq 3x^2 \leq 3x^2+x+1$$ for all $x \geq 0$.

• For all $\varepsilon>0$, we have \begin{align*} (1+\varepsilon) 3x^2 &= 3x^2+3\varepsilon\ x^2 \\ & \geq 3x^2+x+1 & \text{whenever } 3\varepsilon\ x^2 \geq x+1. \end{align*} We see that $3\varepsilon\ x^2 \geq x+1$ is true whenever $x^2-\tfrac{1}{3\varepsilon}x-\tfrac{1}{3\varepsilon} \geq 0$. We see that \begin{align*} x^2-\tfrac{1}{3\varepsilon}x-\tfrac{1}{3\varepsilon} &\geq x^2-\tfrac{2}{3\varepsilon}x & \text{when } x \geq 1\\ & \geq x^2-x^{3/2} & \text{when } \sqrt{x} \geq \tfrac{2}{3\varepsilon} \\ & \geq 0 & \text{when } x \geq 1. \end{align*}

We conclude that, if $C_1 \in (0,1]$ and $C_2\ \in (1,\infty)$, then $$C_1\ g(x) \leq f(x) \leq C_2 g(x)$$ for all sufficiently large $x$.