2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Do you need the asymptotic complexity ($O$, $\Theta$)? $\endgroup$
    – Paresh
    Feb 12, 2013 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, 2013 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, 2013 at 20:21

2 Answers 2

4
$\begingroup$

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

$\endgroup$
5
  • $\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, 2013 at 21:51
  • $\begingroup$ Nevermind, answered my own question^^ $\endgroup$
    – furlessxp
    Feb 12, 2013 at 21:54
  • $\begingroup$ Glad I could help! $\endgroup$
    – Paresh
    Feb 12, 2013 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, 2013 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, 2013 at 10:13
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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