I'm given the equation $(n^2+1)^{10}$

I have to find it's efficieny class, and prove it: It looks to be $Big Theta (n^{20})$

I've tried this using limits:

$\lim_{n\to\infty}(n^2+1)^{10}/n^{20} = \lim_{n\to\infty}(n^2+1)^{10}/n^{2(10)} = \lim_{n\to\infty}((n^2+1)/n^2)^{10}$

And looking at the problem, I thought the answer is 0, because when n is infinity, and is plugged in, we're diving a small numerator by a large denominator, which should give zero. And since it's less than $C> 0$, the original equation would not be theta($n^{20}$).

However, after looking at the textbook answer, the answer is actually 1, meaning it is indeed theta($n^{20}$).But I really don't understand why? I'm not sure how that's the case even with the exponent, isn't a small number divided by infinity always going to equal zero?

  • $\begingroup$ What is the limit of $\frac{n^2}{n^2}$ as $n\to\infty$? And what is that of $\frac{n^2+1}{n^2}$? In general what is the limit to the quotient of two polynomial as $n\to\infty$? $\endgroup$ – Thibaut Dumont Feb 15 '17 at 18:36
  • $\begingroup$ They're all 1? It still doesn't make sense to me. $\endgroup$ – erefeofkeo Feb 15 '17 at 18:37
  • $\begingroup$ I edited your calculation: The numerator is suppose to be $n^2+1$, not $1+1$. $\endgroup$ – Thibaut Dumont Feb 15 '17 at 18:38
  • $\begingroup$ So that would give me (1 + 1/n)^10 = , right I see it now. $\endgroup$ – erefeofkeo Feb 15 '17 at 18:40
  • $\begingroup$ Rather $(1+1/n^2)^{10}$, but it goes to $1$ indeed. $\endgroup$ – Thibaut Dumont Feb 15 '17 at 18:41

Your Answer

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

Browse other questions tagged or ask your own question.