# Difference between revisions of "TADM2E 2.35"

From Algorithm 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.) |
Letientai299 (Talk | contribs) (Correct the function again. The implementation in previous edit has 2 mistakes: `n` and `2*i` are excluded. The problem states that `for i=1 to n do`, which should mean `n` is included. Same for `2*i`) |
||

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> |

## Latest revision as of 17:56, 14 October 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} $