I'm new to analyzing algorithms and I'm having trouble translating this while loop into a summation:
c = 0
n = n - 2
while n > 0 c = c + (2 * n) n = n - 2
endAt first, I thought that it would be $$\sum_{n=1}^{n-2} 2(n-2)$$
but I'm don't think this is correct since I'm not accounting for the decrement by 2.
$\endgroup$ 02 Answers
$\begingroup$You have two problems. One is the decrement by $2$, as you suggest. If you start with $n=10$ the loop gets evaluated with $n$ equal to $8,6,4,2$. If you start with $n=9$ the loop gets evaluated with $n$ equal to $7,5,3,1$. It is good to write out small cases to make sure you get them right. The usual mathematical summation does not have a step value the way computer loops do. You need to reflect that by multiplying the index by the step you want. I will assume that $n$ is even in what follows and leave to you the fixes needed when $n$ is odd. We need to count from $2$ to $n-2$ by $2$s, which we write as counting from $1$ to $\frac {n-2}2$ and doubling the number. The second problem is that you should just be adding in the value $2n$, not $2(n-2)$, so the sum becomes $$\sum_{k=1}^{\frac {n-2}2}4k$$ where one factor of $2$ comes from the fact that $n=2k$ and the other from the $2n$ in the code.
$\endgroup$ $\begingroup$So, first of all, is the initial $n$ odd or even? Because if it is even, then you cannot start the counter at 1, you have to start it at 2.
Take $K=\lfloor n/2\rfloor$ the floor of half the initial $n$. Then, if you do $1+2k$ with $k$ from 0 to $K$ you will get the sequence $1,3,5,\dots,1+2*K$.
Now, each term of the sum you are adding $2*n_k$, where $n_k$ is the corresponding term of the sequence, aren't you?
Together, $$\sum_{k=0}^{\lfloor n/2\rfloor}2(2k+1).$$
$\endgroup$ 1
