# Big theta notation question

I want to prove that $$(n+a)^2 = \Theta(n^2).$$ I know I have to show that $c_1 g(n) \le f(n) \le c_2 g(n)$ , which means I have to show $c_1 n^2 \le (n+a)^2 \le c_2 n^2$.

Firstly , I know for the Big O part $$c_2 \ge (n+a)^2 / n^2 \ge (n + n )^2 /n^2 = 4n ^2/n^2 = 4,$$ for $n \gt 0$.

How can I find $c_1$ such that $c_1 \le (n+a)^2/n^2$ so that I can complete my proof ? Thanks.

• I don't think your calculation for $c_2$ is correct: you are interested in what's happening as $n$ gets big, while $a$ is constant. So how do you justify $(n+a)^2 / n^2 \ge (n + n )^2 /n^2$? – NickD Apr 22 '17 at 14:31
• @Nick Hello Nick , well I am not pretty sure what to do here ..but for reference I had seen this online having a similar problem and check exercise 3.1-2 if u dont mind csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf – Johnathan Apr 22 '17 at 16:33
• You've got the wrong end of the stick: try starting with the other inequality and do the $\Omega$ part first. That's similar to what you did above (except for the direction of the inequalities of course). After you've done that, then start worrying about the $O$ part. – NickD Apr 22 '17 at 23:59

Your $O(n^2)$ proof doesn't work, because eventually $n>a$ and the inequality no longer holds. One may reason as follows: $$\frac{(n+a)^2}{n^2} = \frac{n^2+2an+a^2}{n^2} = 1 + \frac{2a}{n}+\frac{a^2}{n^2}.$$ Once $n>k\lvert a\rvert$, we have $\lvert a\rvert/n<1/k$, so $$\left| \frac{2a}{n}+\frac{a^2}{n^2} \right| < \frac{2\lvert a\rvert}{n}+\frac{\lvert a\rvert^2}{n^2} < \frac{2}{k}+\frac{1}{k^2}.$$ Both of these tend to zero, so if we choose $k$ large enough, this is smaller than $1/2$. Then $$\left| \frac{(n+a)^2}{n^2} -1 \right| < \frac{1}{2},$$ or $$\frac{1}{2} < \frac{(n+a)^2}{n^2} < \frac{3}{2} \\ \frac{1}{2}n^2 < (n+a)^2 < \frac{3}{2}n^2,$$ as required.
$n>2|a|\implies\frac 12n<\big||n|-|a|\big|\le|n+a|\le|n|+|a|< 2n\implies \frac {n^2}{4}<(n+a)^2<4n^2$