How to read this math equation? $\sum_{i=0}^{n-2}(n-1-i)$

Question

I stumbled upon this in a book and am uncertain how to read it. This is in the context of describing run-time complexity of a computer algorithm.

$$\sum_{i=0}^{n-2}(n-1-i)$$

Answer 1

The symbol $$ \sum $$ means "sum". So this is a compact way of writing a long sum (addition) of a bunch of things. The sum has an index variable which starts somewhere and ends somewhere. For example, $$ \sum_{i=1}^5 $$ means, start at $i=1$, and end at $i=5$, and add up all the terms.

Now for the full notation, with some examples: $$ \sum_{i=1}^5 (i + 1) $$ means the sum of five things, $(i+1)$ where $i$ starts at $1$ and goes up to $5$. So it's equal to $$ (1 + 1) + (2 + 1) + (3 + 1) + (4 + 1) + (5 + 1). $$ That evaluates to $2 + 3 + 4 + 5 + 6 = 20$.

Now we can do your example: $$ \sum_{i=0}^{n-2}(n-1-i) $$

This says to start at $i=0$, and end at $i = n-2$, and add up $n-1-i$. So it equals $$ (n-1-0) + (n-1-1) + (n-1-2) + (n-1-3) + \cdots + (n-1-(n-3)) + (n-1-(n-2)). $$ For example, if $n = 5$, then we get $$ \sum_{i=0}^{3}(4-i) = (4-0) + (4-1) + (4-2) + (4-3) = 4 + 3 + 2 + 1 = 10. $$

Answer 2

Assuming that you are familiar with summation notation, the expression that you provided is to be interpreted as follows: \begin{align} \sum_{i=0}^{n-2} \left( n - 1 - i \right) &= (n-1-0) + (n-1-1) + (n-1-2) + \cdots + (n-1-(n-3)) + (n-1-(n-2)) \\ &= (n-1) + (n-2) + \cdots + (2) + (1) \end{align} This sum can be expressed slightly more succinctly by

$$ \sum_{i=0}^{n-2} \left( n - (i+1) \right) = \sum_{i=1}^{n-1} \left( n - i \right) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} $$

Note that $n$ is an unbounded or "free" variable defined by the context of the expression.