Sigma Notation multiple sigma

Question

I'm an engineer students, I want to now the runtime of loop inside loop, I get the calculation in sigma notation like the picture above. Can somebody explain to me how sigma inside sigma can be like this? For example how (i^2-1) can be (i^4-i^2) Sorry for bad English.

Answer 1

Note that $$\sum_{j=0}^{n}j=\sum_{j=1}^{n}j=\frac{n(n+1)}{2}.$$ Now setting $n=i^2-1$ gives you $$\sum_{j=0}^{i^2-1}j=\frac{(i^2-1)((i^2-1)+1)}{2}=\frac{(i^2-1)i^2}{2}=\frac{i^4-i^2}{2}.$$

Answer 2

Your formula being $$T(n)=\sum_{i=0}^{n-1}\sum_{j=0}^{i^2-1}\sum_{k=0}^{j-1}c$$ Let us start with the most inner loop $$\sum_{k=0}^{j-1}c=cj$$ So, $$T(n)=c\sum_{i=0}^{n-1}\sum_{j=0}^{i^2-1}j$$ For the remaining inner loop,as said (Faulhaber formula) $$\sum_{j=0}^m j=\frac{1}{2} m (m+1)$$ which makes (replacing $m$ by $i^2-1$) $$\sum_{j=0}^n j=\frac{1}{2}(i^4-i^2)$$ So, what is left is $$T(n)=\frac{1}{2}\sum_{i=0}^{n-1}(i^4-i^2)=\frac{1}{2}\sum_{i=0}^{n-1}i^4-\frac{1}{2}\sum_{i=0}^{n-1}i^2$$ Again Faulhaber formulas $$\sum_{i=0}^{n-1}i^4=\frac{1}{30} (n-1) n (2 n-1) \left(3 n^2-3 n-1\right)$$ $$\sum_{i=0}^{n-1}i^2=\frac{1}{6} (n-1) n (2 n-1)$$ So, after simplifications $$T(n)=\frac{c}{20} n \left(2 n^4-5 n^3+5 n-2\right)=\frac{c}{20} (n-2) (n-1) n (n+1) (2 n-1)$$ or $$T(n)=\frac{c}{20}n^5\big(2-\frac{5}{n}+\frac{5}{n^3}-\frac{2}{n^4})$$