7
$\begingroup$

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 ≤ C1$n^2$ ≤ 2$n^2$ - 4n + 7 ≤ C2$n^2$

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

0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

Split the problem into two parts: LHS and RHS.

We start with the RHS:

Find constant C2 that will satisfy

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

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 C2 to be 2, n≥2 to satisfy the RHS.

LHS: we try to find a constant that will satisfy

0 ≤ C1 ≤ 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 C1 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

C1 = 1 , C2 = 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 C1 to also be 2, wouldn't that also satisfy the left hand side since the inequality allows it to be ≤?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot. I was just wanting to make sure that I wasn't overlooking something. Since I'm new to this it's hard to tell when I'm right since theres multiple solutions. $\endgroup$ – Harrison Nguyen Sep 16 '13 at 0:20
  • $\begingroup$ That's actually a really helpful insight into how to write better proofs. It seems that this is the way most proofs are written in the textbook that I'm using. It caused me to get stuck for a while figuring out how they magically pulled the value of the constants out of thin air. Noted for next time. $\endgroup$ – Harrison Nguyen Sep 16 '13 at 0:27
  • $\begingroup$ In a sense, the multiple solutions are how you know it's "right". You/we are starting to get into the more theoretical science, where you believe that you have a model which explains phenomena. For example, you believe (but don't truly know) that "Big Theta", consistent with math and logic and so on, describes computational complexity. Your solution substantiates that belief. Other solutions substantiate it further. Thus a scientific consensus is created. $\endgroup$ – AndrewK Sep 16 '13 at 2:44
  • $\begingroup$ DW's observation about proof-writing is astute, and I'd take it a step further (time permitting). Rather than having just a side calculation, have each way of writing be a branch, and run them in parallel to completion. If you goof, the contradiction should jump right out. If you don't goof, you've got one helluvan explanation. $\endgroup$ – AndrewK Sep 16 '13 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.