1
$\begingroup$

I am trying to figure out the time complexity of the a given Algorithm, but using summations. Can anyone help get started on the inner summation, because I haven't come across such summation yet, and we just began solving these.

$$\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^{j} n $$

$\endgroup$
  • $\begingroup$ Since the answer to the question does not depend on the algorithm, I think it is more appropriate to tag it to summation instad of algorithms and computational complexity since this isneither a question on algorithms nor on complexity theory. $\endgroup$ – Fawzy Hegab Jan 26 '17 at 19:45
  • $\begingroup$ We were given an algorithm and going through the for loops, I obtained these summations, either way thanks. $\endgroup$ – Kono Dio Da Jan 26 '17 at 19:49
3
$\begingroup$

Consider the inner summation. Note that it is indexed by $k$, meaning that $k$ is variable in this summation while everything else is constant. In particular, $n$ is a constant. Therefore $$\sum_{k=1}^j n = n\sum_{k=1}^j1 = nj.$$

In light of the previous calculation, in the second summation we would like to compute

$$\sum_{j=i}^{n+i}\sum_{k=1}^j n = \sum_{j=i}^{n+1}nj = \sum_{j=1}^{n+1}nj-\sum_{j=1}^{i-1}nj.$$

Here the variable in the summation is $j$, so again we can pull $n$ in front to get

$$\sum_{j=1}^{n+1}nj-\sum_{j=1}^{i-1}nj = n \left(\sum_{j=1}^{n+i}j-\sum_{j=1}^{i-1}j\right) = n \left(\frac{(n+i)(n+i+1)}{2} - \frac{(i-1)i}{2}\right).$$

Note that a well known formula for summing the number from 1 to m (see https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_⋯)

Finally, the outer summation. We would now like to compute

\begin{align*} \sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n &= \sum_{i=1}^{2n}n \left(\frac{(n+i)(n+i+1)}{2} - \frac{(i-1)i}{2}\right)\\ & = \sum_{i=1}^{2n}\frac{n^3+2n^2i+n^2+2ni}{2}. \end{align*}

In this summation, the variable is $i$ so we can factor out multiplicative factors of $n$. After breaking up the long fraction, this gives us

\begin{align*} &=\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n\\ &=\frac{n^3}{2}\left(\sum_{i=1}^{2n}1\right)+n^2\left(\sum_{i=1}^{2n}i\right)+\frac{n^2}{2}\left(\sum_{i=1}^{2n}1\right)+n\left(\sum_{i=1}^{2n}i\right)\\ & = \frac{n^3}{2}\left(2n\right)+n^2\left(\frac{2n(2n+1)}{2}\right)+\frac{n^2}{2}\left(2n\right)+n\left(\frac{2n(2n+1)}{2}\right), \end{align*} where I used the same formula to sum the number 1 to 2n, and I used this other well known formula $$\sum_{i=1}^n i^2 = \frac{i(i+1)(2i+1)}{6}.$$ for summing the numbers $1^2, 2^2,..., (2n)^2$ (see https://proofwiki.org/wiki/Sum_of_Sequence_of_Squares ).

So I'm sure you'll want to reduce this, but the summation is above.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah thank you very much! Those links will help me a lot. $\endgroup$ – Kono Dio Da Jan 26 '17 at 19:46
  • 1
    $\begingroup$ In the question posted, the summation for $j$ runs from $\color{red}i$ to $n+i$, not $1$ to $n+i$. $\endgroup$ – Hypergeometricx Jan 31 '17 at 11:31
  • $\begingroup$ Thanks. I'll make the change $\endgroup$ – JSP Jan 31 '17 at 19:30
2
$\begingroup$

If you just want time complexity, a $O(n^k)$ for some $k$ might be good enough.

The following uses the trivial bound (for $n > 1$) $\sum_{i = 1}^n i^k \lt \sum_{i = 1}^n n^k = n^{k+1} $.

$\begin{array}\\ \sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^{j} n &=\sum_{i=1}^{2n}\sum_{j=i}^{n+i}jn\\ &=\sum_{i=1}^{2n}n\sum_{j=i}^{n+i}j\\ &<\sum_{i=1}^{2n}n(n+i)^2\\ &<\sum_{i=1}^{2n}n(n^2+2ni+i^2)\\ &=\sum_{i=1}^{2n}n^3+\sum_{i=1}^{2n}2n^2i+n\sum_{i=1}^{2n}i^2\\ &=2n^4+2n^2\sum_{i=1}^{2n}i+n\sum_{i=1}^{2n}i^2\\ &<2n^4+2n^2(2n)^2+n(2n)^3\\ &=(2+4+8)n^4\\ &=14n^4\\ \end{array} $

So the total is $O(n^4)$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$$\begin{align} \sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n &=n\sum_{i=1}^{2n}\sum_{j=i}^{n+i}j\\ &=n\sum_{i=1}^{2n}\sum_{r=0}^n (r+i) &&(r=j-i)\\ &=n\left[\sum_{i=1}^{2n}\sum_{r=0}^n r+\sum_{r=0}^n \sum_{i=1}^{2n}i\right]\\ &=n\left[2n\cdot \frac {n(n+1)}2+(n+1)\cdot \frac {(2n)(2n+1)}2\right]\\ &=\color{red}{n^2 (n+1)(3n+1)=\mathcal{O}(n^4)} \end{align}$$

| cite | improve this answer | |
$\endgroup$

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.