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

Leave a Reply

Your email address will not be published. Required fields are marked *