Running time of a nested loop with $\sum i \log i$ term

Question

So I have the following pseudo-code:

Function(n):
for (i = 4 to n^2):
 for (j = 5 to floor(3ilog(i))):
 // Some math that executes in constant time

So far, I know that to find this i will be calculating

$\sum_{i=4}^{n^2}\sum_{j=5}^{3i \log_{2}i}C$ where $C$ is a constant, but I am completely lost as to how to proceed past the first summation which, if I'm not mistaken, will give me 3ドルC \cdot (\sum_{i=4}^{n^2}(i \log_{2}i) - 5(n^2 - 4)),ドル but from here I'm lost. I don't need exact running time, but the asymptotic complexity.

All help is greatly appreciated! I realize that this might be a duplicate, but I haven't been able to find a nested for loop problem of this nature anywhere...

• Paresh: Do you need the asymptotic complexity ($O,ドル $\Theta$)?
• furlessxp: Yes, that is it, we are looking for Big Theta, I will go ahead and edit the post.
• Joe: First step, distribute the subtraction, and pull out the 3, so that the most complicated piece left to evaluate is $\sum_i i \log i$

Answer 1

$$F(n) = \sum\limits_{i = 4}^{n^2} \sum\limits_{j = 5}^{3i\log i}C = C\sum\limits_{i = 4}^{n^2}(3i\log i - 4) = 3C\sum\limits_{i = 4}^{n^2}i \log i - \Theta(n^2)$$

For asymptotic analysis, we can start the summation from $i = 1$ instead of 4ドル$. Let

$\begin{align} T(n) &= \sum\limits_{i = 1}^{n^2}i\log i = \sum\limits_{i = 1}^{n^2}\log {i^i} \\ &= \log {1^1} + \log {2^2} + \log {3^3} + \dots + \log {(n^2)^{n^2}} \\ &\le n^2 \cdot \log (n^2)^{n^2} \ \ \text{(there are \(n^2\) terms)}\\ &= 2n^4 \log n \\ &= O(n^4 \log n) \end{align} $

Now, since $f(x) = x\log x$ is a continuous increasing function in $x \in [1, \infty),ドル you can verify that :
$\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \ \ $ (changing $i$ to $x$ simply because $x$ looks better when integrating).

According to Wolfram, $\int\limits_{1}^{n^2}x\log x \ dx = \frac{1}{4}\left(n^4 \log \left({\frac{n^4}{e}}\right) + 1\right) = n^4 \log \left({\frac{n}{e}}\right) + \frac{1}{4}$

Therefore, $\sum\limits_{x = 1}^{n^2}x\log x = \Omega(n^4\log n)$.

Combining the upper and lower bounds, we have $T(n) = \Theta(n^4\log n)$

Overall, $F(n) = \Theta(n^4\log n) - \Theta(n^2) = \Theta(n^4 \log n)$.

So, your loops have complexity $\Theta(n^4 \log n)$.

Remarks:
1. You can show the lower and upper bounds in a similar way by observing that: $\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \le \int\limits_{0}^{n^2}(x+1)\log {(x+1)} \ dx$
2. For the above inequalities, you can use the method of Riemann sum (use the left and the right Riemann sums to see the two bounds). Draw unit-width rectangles on an increasing function to see these bounds.
3. I have done some implicit simplifications, such as just ignoring the constant 3ドルC$ term, or starting the summation from 1ドル$ instead of 4ドル$ since we are dealing with $\Theta$. I have also made the common but slight abuse of notation when equating or subtracting $\Theta$ terms, without affecting the answer.

• furlessxp: This is beautiful! Quick question, how do you arrive at the very first inequality? I can see that there are $n^2$ terms, but how exactly does that mean that multiplying by $n^2$ makes it greater than or equal to the summation?
• furlessxp: Nevermind, answered my own question^^
• Paresh: Glad I could help!
• furlessxp: If the outer summation were to go from $n$ to $n^2$ instead of just starting at a constant, would we still be able to start at 1? Or does that require more calculations?
• Paresh: @furlessxp No, you should not start from 1ドル$ in that case. However, the answer should not change. I haven't calculated it, but you should get two terms - $O(n^4\log n) - O(n^2\log n)$ as both the upper and lower bounds. So, the expression should still be $\Theta(n^4\log n)$.

Answer 2

Let $N=n^2,ドル let's compute the sum $S=\sum\limits_{i=1}^{N} i \ln i=\sum\limits_{i=1}^{N} \ln i^i$

$S=\ln 1 + \ln 2^2 + \ln 3^3 + \dots+\ln N^N=\ln (1\times 2\times 2 \times 3 \times 3 \times 3 \times \dots)$

$=\ln (N!\times N!/2!\times N!/3! \times \dots)=N\ln N! - \Theta(1)$

Using Stirling's formula we get:

$S=N(N\ln N - N + O(\ln N)) - \Theta(1) = \Theta(N^2\ln N)$

Now replace $N$ by $n^2$:

$S=\Theta(n^4\ln n^2)=\Theta(n^4 \ln n)$