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.


migrated from stackoverflow.com Sep 9 '12 at 23:03

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ 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$ $\endgroup$ – Belgi Sep 9 '12 at 23:08

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?

  • $\begingroup$ So, for the inequality n^2 + 8n <= c2*n^2 I could pick c2 = 2, and then show that it holds after N = 8? My thinking is that I could compare the second terms, n^2 + 8n <= n^2 + n^2 (equivalent to c2 = 2, or 2*n^2), and then finding an N such that 8n <= n^2, such as N = 8. Is that correct? All I have to do is show that these numbers exist? $\endgroup$ – Vance Sep 10 '12 at 6:11
  • $\begingroup$ @vance. You got it, Grasshopper. $\endgroup$ – Rick Decker Sep 10 '12 at 12:53

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.