Difference between revisions of "TADM2E 2.35"
From Algorithm Wiki
(Recovering wiki) |
(Corrected function so that output matches reality. See https://gist.github.com/jaytaylor/1bc35d0a07181877e0d486faebdc6f6b#file-algorithms-design-manual-solutions_tadm2e-2-35-py-L13 for proof.) |
||
| Line 17: | Line 17: | ||
\begin{align} | \begin{align} | ||
&T(n)=\sum_{i=1}^{n}\sum_{j=i}^{2*i}1=\sum_{i=1}^{n}(2i-i+1)= | &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} | + | \sum_{i=1}^{n}(i+1)=\frac{n(n+1)}{2}-n |
\end{align} | \end{align} | ||
</math> | </math> | ||
Revision as of 20:57, 21 July 2016
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} $
