[Math] Getting a summation formula from a while loop

algorithms

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
end

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

Best Answer

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.

Related Question