Algorithm Analysis: How to simplify a summation leading up to a maximal term?

Question

Okay so I have a summation which goes:

$$\sum_{i=1}^{n^3} 3i^2\cdot\log(i)$$

My goal is to find the order of the function, not the exact summation amount. I have found the order of it by writing out the sum, and noticing that my maximal term from the sum is $3(n^3)^2\log(n^3)$.

Therefore, I am looking at the entire summation as order $(n^6)\log(n)$. Can it be simplified this way, or does the large "amount" of terms being summed (after all, it is going from $i=1$ all the way to $i=n^3$) lead to the overall order of the function being higher than this? And if this is the case, does anyone giving pointers as to how to accomplish this?

Saying it another way, there are a ton of terms being summed up here. Does just taking the maximum term from the summation constitute the highest order of the summation, or does adding together so many such terms result in a higher order?

A common example is to view the series $1+2+3+ \dots +n$. As we know, this is not order $n$. This is order $n^2$, because of the lemma which states that this series is equal to $n(n+1)/2$. So this is where my concern is coming from.

Answer 1

I do not know how this could help you but the summation you consider has a closed form which can write

$$ \frac{3\,\zeta(3)}{4 \pi^2} + \zeta'(-2, 1 + n^3) $$

where $\zeta'(a,b)$ represents the derivative of $\zeta(a,b)$ (the generalized Riemann Zeta function) with respect to "$a$".

Answer 2

A possible estimate can be made from an integral for which the sum would provide an approximation, e.g.,

$$3 \int_1^{n^3} di \, i^2 \log{i} = \left [i^3 \log{i} \right ]_1^{n^3} - \frac13 \left [i^3\right ]_1^{n^3}$$

This is then $O\left ( n^9 \log{n}\right )$, as you might have suspected.

Answer 3

Let $x_i=3i^2\log(i)$ then the sequence $(x_i)$ is nondecreasing hence $$ (k/2)x_{k/2}=\sum_{i=k/2}^kx_{k/2}\leqslant\sum_{i=1}^kx_i\leqslant kx_k.$$ Since $x_{k/2}=\Theta(x_k)$, this yields $$ \sum_{i=1}^kx_i=\Theta(kx_k).$$ In the case at hand, $k=n^3$ hence $kx_k=3n^9\log(n^3)$ hence $$ \sum_{i=1}^kx_i=\Theta(n^9\log n). $$ To get an exact equivalent of the partial sums, note that $x_i=u(i)$ for every $i\geqslant1$, where the function $u:t\mapsto3t^2\log t$ is nondecreasing on $t\geqslant1$ hence, for every $i\geqslant2$, $$ \int_{i-1}^iu(t)\mathrm dt\leqslant\int_{i-1}^iu(i)\mathrm dt= x_i=\int_i^{i+1}u(i)\mathrm dt\leqslant\int_i^{i+1}u(t)\mathrm dt. $$ Since $x_1=0$, summing these yields $$ \int_1^ku(t)\mathrm dt\leqslant\sum_{i=1}^kx_i\leqslant\int_1^{k+1}u(t)\mathrm dt. $$ Note that $u=v'$ where $v:t\mapsto t^3\log t-\frac13t^3$ hence $v(k)\sim v(k+1)\sim k^3\log k$. Using this for $k=n^3$ yields $$ \sum_{i=1}^{n^3}x_i\sim (n^3)^3\log(n^3)=3n^9\log n, $$ in the precise sense that $$ \lim_{n\to\infty}\frac1{n^9\log n}\sum_{i=1}^{n^3}3i^2\log i=3. $$

Answer 4

In short/in general: The order of the last term in the summation is not necessarily the order of the sum. What you found with the Harmonic sum (and with this sum) exemplifies that.

For the problem at hand:
I'm going to approach this from a CS competition perspective. That is, I'm going to give some rough bounds for the algorithm, even though I know they're not exact. This is useful in ACM-style competitions when you want to know quickly if you need to re-structure your solution.

For an upper bound, we can note that $\log(i) < i$ (for large enough $i$). Then, our sum becomes: $$\sum_{k=1}^{n^3}i^2\log(i)\approx\sum_{k=1}^{n^3}i^3 = \left(\frac{n^3(n^3+1)}{2}\right)^2 \approx \mathcal{O}(n^{12})$$

A lower bound is (by eliminating the log term): $$\sum_{k=1}^{n^3}i^2\log(i)\approx\sum_{k=1}^{n^3}i^2 = \frac{n^3(n^3+1)(2n^3+1)}{6} \approx \Omega(n^{9})$$

This method of upper/lower bounds is oftentimes helpful enough, so I thought I'd include it here for future readers.