Finding the complexity of a decimal power

Question

How can I find the complexity of $n^{3.5} - (n-3)^{3.5}$ The complexity looks like it will be nearly 0? But I have no idea how to find a tight bound for this function.

Answer 1

I assume you want to let $n\rightarrow \infty$ or $\frac{1}{n}\rightarrow 0.$ I give the result for general exponent $a$. $$n^a - (n-3)^a= \frac{1}{\left(\frac{1}{n}\right)^a} -\frac{\left(1-\frac{3}{n}\right)^a}{\left(\frac{1}{n}\right)^a}\\ =\frac{1}{\left(\frac{1}{n}\right)^a}\left(1-\left(1-\frac{3}{n}\right)^a\right) $$ Now use the https://en.wikipedia.org/wiki/Binomial_series $$n^a - (n-3)^a\sim \frac{1}{\left(\frac{1}{n}\right)^a}\left(1-\left(1-a\frac{3}{n}\right)\right) =3a n^{a-1}\quad (n\rightarrow \infty)$$ If you substitute $a=3.5=7/2$ you get $$n^{7/2} - (n-3)^{7/2} \sim \frac{21}{2}n^{5/2}$$

As an example: the quotient RHS/LHS is $\approx 1.038\;$ for $n=100\;$ and $\approx 1.004\;$ for $n=1000.$