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