# Test 1 #5 (Version A)

Use the definition of big-$Theta$ notation to determine whether $f(x)=x^2$ is $\Theta(x^3)$.

To show that $f(x)=x^2$ is $\Theta(x^3)$, we would have to show that $f(x)=x^2$ is $O(x^3)$ and that $f(x)=x^2$ is $\Omega(x^3)$.

However, we can see that $f(x)=x^2$ is not $\Omega(x^3)$, as follows:

(This will be a proof by contradiction). Assume that $f(x)=x^2$ is $\Omega(x^3)$. This means that there exists a pair of positive constants $(C,k)$ such that, for all $x>k$, we have that $|x^2| \geq C|x^3|$.
Since $k>0$ and $x>k$ we have that $x^2>0$.
This means that we are assuming that $x^2 \geq Cx^3$ for all $x>k$.
It also means that we can safely divide both sides of the inequality by $x^2$ without changing it.
This gives that $1 \geq Cx$ for all $x>k$.
Since $C>0$, this means that $\frac{1}{C} \geq x$ for all $x>k$.
Whatever $C$ is, it’s just a constant, so $\frac{1}{C}$ is also just a constant. So this is saying that for all large values of $x$, $x$ stays below the constant $\frac{1}{C}$. This is a contradiction, so our initial hypothesis, that $f(x)=x^2$ is $\Omega(x^3)$, must have been false.

Since $f(x)=x^2$ is not $\Omega(x^3)$, $f(x)=x^2$ cannot be $\Theta(x^3)$.

This entry was posted in Test #1 Solutions. Bookmark the permalink.

### 1 Response to Test 1 #5 (Version A)

1. Kate Poirier says:

Many of you had the correct answer, but didn’t justify it. To show that $f(x)=x^2$ is *not* $\Omega(x^3)$, you have to show that there is *no possible pair* $(C,k)$ such that the condition in the definition is satisfied. It’s not enough to pick a value for $C$ and show that it has no partner $k$. It’s also not enough to pick a value for $C$ and a value for $k$ and show that they do not satisfy the condition in the definition.

A few of you included a proof that $f(x)=x^2$ is $O(x^3)$, which is true but not necessary since $f(x)=x^2$ is not $\Omega(x^3)$.