Steps in Simplifying summations

Question

I am trying to order functions in increasing asymptotic order. However I have some summations such as $\sum_{i=1}^{n} i^{77}$ which I cannot find the intuition to compare it to a function like $\log^{\sqrt{\log(n)}}{n}$. It was demonstrated to me that $\sum_{i=1}^{n} i^{77}$ can be simplified to $\theta(n^{78})$ and $\sum_{i=1}^{n} \frac{1}{i} = \log{n}$ but I did not follow.

How do I reproduce this result? Also how would I simplify: $$\sum_{i=1}^{n} \frac{i^{2} + 5i}{6i^{4} + 7}$$

Answer 1

Here are some tricks helpful for determining asymptotic orders:

• $\sum_{i=1}^n f(i)$ has the same order as $\int_0^nf(x)\,dx$, provided $f$ is either an increasing or decreasing function. For example, $\sum_{i=1}^n i^{77}$ is like $\int_0^n x^{77}\,dx=\frac1{78}n^{78}$. You can also use $\int_1^nf(x)\,dx$, which is useful for $\sum_{i=1}^n \frac1i$ because $1/x$ cannot be integrated from $0$.

• If $\sum_{i=1}^n f(i)$ is complicated, instead look for a simple function $g(i)$ such that $\lim_{i\to\infty} \frac{f(i)}{g(i)}=1$. For such a $g$, you have that $\sum_{i=1}^n f(i)$ is asymptotically equivalent to $\sum_{i=1}^n g(i)$. In your last example, $$\frac{i^2+5i}{6i^4+7}=\frac1{6i^2}\cdot \Big(\frac{1+\frac{5}{i}}{1+\frac{7}{i^4}}\Big)$$Since the part in parentheses converges to $1$ as $i\to\infty$, $\sum_{i=1}^n\frac{i^2+5i}{6i^4+7}$ will have the same asymptotic growth as $\sum_{i=1}^n \frac1{6i^2}$. Since $\int_1^n \frac1{6x^2}\,dx=\frac16(1-\frac1n)$, this summation is $O(1)$.

• If there is something complicated in an exponent, try taking logs; this will preserve the asymptotic order. For example, when asking which of the following is asymptotically bigger:$$(\log n)^{\sqrt{\log n}}\qquad \text{or}\qquad n^{\log \log n},$$take logs of both sides to get$${\sqrt{\log n}}\cdot \log \log n\qquad \text{or}\qquad {\log \log n}\cdot \log n,$$and observe that function on the right is larger since $\sqrt{\log n}$ is $o(\log n)$.