Big Theta Proof on polynomial function

Question Detail: 

This is not homework. I have the solution but it's not what I'm getting. I know there are multiple solutions to the problem but I want to make sure that I'm not missing anything.

The question is as follows:

Prove that 2$n^2$ - 4n + 7 = Θ ($n^2$). give the values of the constants and show your work.

Here is how I approached the problem:

From the definition of Θ(g(n)):

0 ≤ C₁$n^2$ ≤ 2$n^2$ - 4n + 7 ≤ C₂$n^2$

Divide the inequality by the largest order n-term. (This is the only way I know how to solve these equations.)

0 ≤ C₁ ≤ 2 - (4/n - 7/$n^2$) ≤ C₂

Split the problem into two parts: LHS and RHS.

We start with the RHS:

Find constant C₂ that will satisfy

0 ≤ 2 - (4/n - 7/$n^2$) ≤ C₂

n=1, (2 - (4/1 - 7/$1^2$)) = 5

n=2, (2 - (4/2 - 7/$2^2$)) = 7/4

n=3, (2 - (4/3 - 7/9)) = 13/9

We choose C₂ to be 2, n≥2 to satisfy the RHS.

LHS: we try to find a constant that will satisfy

0 ≤ C₁ ≤ 2 - (4/n - 7/$n^2$)

From above, we know that after n=2, the equation approaches 2 as n grows larger, so if we pick a constant that is less than 2 then it should satisfy the LHS.

We choose C₁ to be 1. For n, choosing 1 would satisfy the left hand side, but since the RHS needs n≥2, we stick with it.

So the constants that prove 2$n^2$ - 4n + 7 = Θ ($n^2$) are

C₁ = 1 , C₂ = 2 , n≥2

The given solution to this problem chooses n≥4, but I'm not sure why. It seems that n≥2 would work fine. Am I wrong somewhere?

If I'm not wrong, if I would have picked C₁ to also be 2, wouldn't that also satisfy the left hand side since the inequality allows it to be ≤?

Asked By : Harrison Nguyen

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14344

Answered By : D.W.

Your solution is fine. There are multiple ways to prove this fact, all of them valid/correct. So your approach is valid, and it's possible that the solution from your class is also valid: that's not a contradiction.

Let me give you one piece of advice for structuring your proof in the future, though. In the argument you sketched in the question, you are "working backwards": you start from the statement you wish were true (that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$), and then you try to derive what needs to be true about $c_1,c_2$ for your wish to hold true. Experience has proven that that kind of reasoning is error-prone, though: it's easy for you to make a mistake along the way. It is also hard for others to check.

When you write up your proof, I suggest you do the reasoning in the opposite direction. Start from what you know is true, and then derive the implications of that, ending with the conclusion that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$. This better matches how people think and makes it easier for the reader to understand what's going on. And the purpose of a proof is to communicate an idea to the reader, so the proof should be structured to make the reader's life easier: to make it as easy as possible for the reader to verify that the proof's reasoning is correct and valid. It's just like a good book; good writing is chosen to make life good for the reader. Proofs are the same way. And, ultimately, this will benefit you too: in my experience, if you follow this approach, then you're less likely to make a subtle mistake in your proof.

So, a better proof outline would be to show that $n^2 \le 2n^2 - 4n + 7$ holds for all $n\ge 2$ (because such-and-such), and show that $2n^2 - 4n + 7 \le 2n^2$ holds for all $n\ge 2$ (because blah-de-blah), and then conclude that $2n^2 - 4n + 7 \in \Theta(n^2)$. I realize this kind of proof is harder to write, because you need to know the value of $c_1,c_2$ to use before you can start writing down this style of proof. But you know what? That's OK. You can do a side calculation, on scratch paper, to figure out what value of $c_1,c_2$ to use. Don't show us that side calculation; just figure out what value of $c_1,c_2$ would be good ones to do, and then start the proof with you pulling $c_1=1,c_2=2$ magically out of thin air, and demonstrate that your choice is valid. This style of proof will be better for you, and better for the reader.