0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – NickD Apr 22 '17 at 14:31
  • $\begingroup$ @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 $\endgroup$ – Johnathan Apr 22 '17 at 16:33
  • $\begingroup$ 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. $\endgroup$ – NickD Apr 22 '17 at 23:59
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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$

$\endgroup$

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.