1
$\begingroup$

So as per the title, I'm trying to prove that a function $f(n) = n^2 + 8n$ exists in $\Theta (n^2)$. What I'm having trouble with is the logic/concept behind doing so.

By definition, it would mean that:

$c_1n^2 \leq n^2 + 8n \leq c_2 n^2 $for constants $c1, c2$, and $N$ such for all $n\geq N$.

I get that. Now, do I just picking random constants that make the equality true? For example, the right side $O$ of the equality would be

$n^2 + 8n \leq c_2n^2$ for all $n \geq N$.

Now, if I let $N = 1$, I could let $n = 1$ also, and therefore the equality becomes $(1)^2 + 8(1) <= c_2(1)^2$, or $9 \leq c_2$. Therefore, $c_2$ could be $9$.

Now, I have proven that there is a $c_2$ and $N$ that makes the right side of the equality hold. I would then use the same $N$ for the left side of the equality, and choose $c_1 = 1$. Is that all is required to prove? How do I really know that my chosen N is correct, such that the equality holds for all $n \geq N$?

I guess what I am asking is if this is indeed a "proper" way to approach proving a function belongs to $\Theta$, or am I missing a concept? Thanks in advance.

  • 0
    You need to pic constants $c_1,c_2$ that works for all $n\geq N$, you chose $N=1$ and then chose $c_1,c_2$, but checked the inquality only for $n=1$ and not all $n\geq N$. Pick any $N$ that you can chose $c_1,c_2$ s.t. for all $n\geq N$ the inquality holds - don't be afraid of choosing a big $N$ if it makes it easier for chhosing $c_1,c_2$ or proving the inquality holds for all $n\geq N$2012-09-09

1 Answers 1

1

Assuming $n>0$, you have two things to show:

  1. There exists a constant $c_1>0$ such that $n^2+8n\le c_1n^2$ for all $n$ large enough.
  2. There exists a constant $c_2>0$ such that $n^2\le c_2n^2+8n$ for all $n$ large enough.

In each, your job is to pick a $c$ and then show that the inequality holds after some $N$ that you compute. For the first, clearly picking $c_1=1$ won't work, since $n^2+8n$ is always greater than $n^2$, but could you pick some larger valuefor your $c_1$? Try one and see what happens. Can you deduce an $N$?

The second inequality is even simpler. What $c_2$ will make $n^2\le c_2(n^2+8n)$ after a certain point? What would $N$ be in this case?

  • 0
    @vance. You got it, Grasshopper.2012-09-10