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.

The OpenLab at City Tech:A place to learn, work, and share

The OpenLab is an open-source, digital platform designed to support teaching and learning at City Tech (New York City College of Technology), and to promote student and faculty engagement in the intellectual and social life of the college community.

The OpenLab at City Tech:A place to learn, work, and share

One Response to Test 1 #5 (Version A)

Kate Poirier says:

March 27, 2016 at 5:18 pm

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)$ .

One Response to Test 1 #5 (Version A)

Leave a Reply to Kate Poirier Cancel reply

Header Image

Recent Posts

Recent Comments

Archives

Categories

Meta

The OpenLab at City Tech:A place to learn, work, and share

Support

Accessibility

Copyright

Creative Commons

The OpenLab at City Tech:A place to learn, work, and share

Support

Accessibility

Copyright

Creative Commons