2.41
1. Three nested summations
[math]\displaystyle T(n)=\sum_{i=1}^{\,n/2}\;\sum_{j=i}^{\,n-i}\;\sum_{k=1}^{\,j}1.[/math]
2. Simplification
Inner-most sum : [math]\sum_{k=1}^{\,j}1=j.[/math]
[math]\displaystyle T(n)=\sum_{i=1}^{\,n/2}\;\sum_{j=i}^{\,n-i}j.[/math]
Evaluate the middle sum:
[math]\displaystyle
\sum_{j=i}^{\,n-i}j
=\frac{(n-i)(n-i+1)}{2}-\frac{(i-1)i}{2}
=\frac{n(n-2i+1)}{2}.
[/math]
Now sum over i:
[math]\displaystyle
T(n)=\frac{n}{2}\sum_{i=1}^{\,n/2}(n-2i+1)
=\frac{n}{2}\Bigl((n+1)\frac{n}{2}-\frac{n}{2}\Bigl(\frac{n}{2}+1\Bigr)\Bigr)
=\frac{n}{2}\cdot\frac{n^{2}}{4}
=\frac{n^{3}}{8}.
[/math]
Therefore
[math]\boxed{T(n)=\dfrac{n^{3}}{8}=\Theta(n^{3})}.[/math]
Back to
Chapter 2
