So I have the following pseudo-code:

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 $3C \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...

  • $\begingroup$ Do you need the asymptotic complexity ($O$, $\Theta$)? $\endgroup$ – Paresh Feb 12 '13 at 20:12
  • $\begingroup$ Yes, that is it, we are looking for Big Theta, I will go ahead and edit the post. $\endgroup$ – furlessxp Feb 12 '13 at 20:13
  • $\begingroup$ 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$ $\endgroup$ – Joe Feb 12 '13 at 20:21

$$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)$.

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 $3C$ 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – furlessxp Feb 12 '13 at 21:51
  • $\begingroup$ Nevermind, answered my own question^^ $\endgroup$ – furlessxp Feb 12 '13 at 21:54
  • $\begingroup$ Glad I could help! $\endgroup$ – Paresh Feb 12 '13 at 21:59
  • $\begingroup$ 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? $\endgroup$ – furlessxp Feb 13 '13 at 2:07
  • $\begingroup$ @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)$. $\endgroup$ – Paresh Feb 13 '13 at 10:13

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)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.