Proving the summation of a function as big theta of another function

Question

Show that $\sum^n_i i^4\log^2i$ = $\Theta(n^5\log^2n)$

I am completely lost on how to solve this problem. I understand that $\Theta$ deals with the upper and lower bounds, so do we prove both big-oh and big-omega?

Answer 1

The summand is a monotone increasing function, so you can compare it with the corresponding integral. Show the order of $\int_{1}^{n} x^4 \log^2 x dx $ using integration by parts.

Answer 2

A simple method:

• lower bound: $$ \sum_{k=1}^n k^4 \log^2 k \geq \sum_{k=\frac{n}{2}+1}^n k^4 \log^2 k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^4 \log^2 \left(\frac{n}{2}\right) = \frac{1}{32} n^5 (\log n-1)^2 $$ as $x\geq 1\mapsto x^4\log^2 x$ is positive and increasing.

  • upper bound: $$ \sum_{k=1}^n k^4 \log^2 k \leq \sum_{k=1}^n n^4 \log^2 n = n^5 \log^2 n $$