1

I'm analyzing the function $f(n) = n^{4.5} - (n-2)^{4.5} $. It has become apparent to me that $f(n) \in \Theta(n^{3.5})$ after experimenting several times on Wolfram Alpha. For more complex expressions of non-polynomial functions that have rational powers like $f(n)$, how can I arrive at the correct growth rate of the function without guessing? Furthermore, how can I solve limits like the one below to prove that the growth rate is true?

$$\lim_{n \to \infty}{\frac{n^{4.5} - (n-2)^{4.5}}{n^{3.5}}}$$

lemon
  • 13

2 Answers2

1

Taylor's expansion gives $$ (n-2)^{4.5} = n^{4.5} - 2\cdot 4.5 n^{3.5} + \frac{2^2}{2} \cdot 4.5 \cdot 3.5 m^{2.5}, $$ for some $m \in [n-2,n]$. In total, this shows that $$ (n-2)^{4.5} = n^{4.5} - 9n^{3.5} + \Theta(n^{2.5}). $$ In particular, $$ \frac{n^{4.5} - (n-2)^{4.5}}{n^{3.5}} = 9 - \Theta(n^{-1}) \to 9. $$

Yuval Filmus
  • 57,157
1

Consider $$A={\frac{n^{4.5} - (n-2)^{4.5}}{n^{3.5}}}$$ Rewrite the numerator as $$n^{4.5}-n^{4.5}\Big(1-\frac{2}{n}\Big)^{4.5}=n^{4.5}\Big(1-\Big(1-\frac{2}{n}\Big)^{4.5}\Big)$$ Now use the fact that, when $x$ is small $(1-x)^a\approx 1-ax$; replace $x=\frac{2}{n} $ and $a=4.5$. So $$1-\Big(1-\frac{2}{n}\Big)^{4.5}\approx 1-\Big(1-\frac{9}{n}\Big)=\frac{9}{n}$$ So $$A \approx \frac{n^{4.5}\frac{9}{n}}{n^{3.5}}=9$$

If, as Yuval Filmus answered, you use Taylor series, you should then find that, for large values of $n$, $$A=9-\frac{63}{2 n}+\frac{105}{2 n^2}+O\left(\left(\frac{1}{n}\right)^{5/2}\right)$$ You could notice that, even for rather small values of $n$, the approximation is not too bad : for example, using $n=10$ gives a value of $6.37500$ while the exact value if $6.33643$; using $n=100$ gives a value of $8.69025$ while the exact value if $8.69021$.

Claude Leibovici
  • 260,315