Algorithm - iterative method

Question

I'm stuck on an exercise on algorithms, can you help me with this exercise?

Solve this recursion using iterative method. $$T(n) = \begin{cases}1 & n=1;\\ 2, & n=2;\\ T(n-2) + n/2,& \text{otherwise}, \end{cases}.$$

I tried to solve this but I got this result:

$$T(n-2\cdot k) + \frac{1}{2}\cdot\sum_{i=0}^{k-1}(n-2\cdot i),$$

$$n-2\cdot k=1\qquad \Rightarrow\qquad k=\frac{n-1}{2}.$$

and I don't know how solve this sum with this $k$?

P.S Sorry on my English I hope you understand me.

Answer 1

I think this type of problem requires backwards substitution starting from $T(n)$.

If $n$ is odd, $ T(n) \\ = T(n-2) + n/2 \\ =(T(n-4) + (n-2)/2)+n/2 \\ =T(n-4) + (n-2)/2+n/2 \\ =(T(n-6) +(n-4)/2)+ (n-2)/2+n/2 \\ = .... \\ =T(1)+3/2+5/2+...(n-2)/2+(n/2)$

If $n$ is even, $T(n) \\ = T(n-2) + n/2 \\ =(T(n-4) + (n-2)/2)+n/2 \\ =T(n-4) + (n-2)/2+n/2 \\ =T(n-6) +(n-4)/2+ (n-2)/2+n/2 \\ =.... \\ =T(2)+4/2+6/2...+(n-2)/2+(n/2)$

• $T(0)$ is not defined, so the backward substitution stops at $T(1)$ and $T(2)$ respectively. $T(1)$ and $T(2)$ can be replaced by 1 and 2 respectively.