Difference between revisions of "TADM2E 2.35"

From Algorithm Wiki
Jump to: navigation, search
(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}+n
+
\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} $