# TADM2E 2.35

From Algorithm Wiki

1. Summations:

for i=1 to n do for j=i to 2*i do output foobar

$ \begin{align} &T(n)=\sum_{i=1}^{n}\sum_{j=i}^{2*i}1\\ \end{align} $

2. Simplification:

$ \begin{align} &T(n)=\sum_{i=1}^{n}\sum_{j=i}^{2*i}1=\sum_{i=1}^{n}(2i-i+1)= \sum_{i=1}^{n}(i+1)=\frac{n(n+1)}{2}-n \end{align} $