0

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

Caleb Stanford
  • 45,895
Taylor Clark
  • 11

2 Answers2

2

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

Caleb Stanford
  • 45,895
  • Thank you. Is there a specific topic I could study more in depth to understand this more in-depth? I vaguely remember seeing it in Statistics but that was many moons ago – Taylor Clark Mar 12 '19 at 01:10
  • @TaylorClark The best place to start would be a discrete math textbook or class. I don't have a specific recommendation, but something like "introduction to discrete math for computer scientists" should turn up useful classes and resources. – Caleb Stanford Mar 12 '19 at 01:13
  • @TaylorClark This Wikipedia article discusses summation notation and list many of the common identities. Since summation notation is just a short hand for repeated addition, you can treat it just as you would a series of terms. Associativity, distribution of multiplication, etc, all still hold. – Brian61354270 Mar 12 '19 at 01:14
1

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.

Brian61354270
  • 2,170