# Appendix: Mathematics Review

A certain familiarity with certain mathematical concepts will help you when trying to analyze algorithms. This section is meant as a review for some commonly used mathematical concepts, notation, and methodology

## Mathematical Notations and Shorthands

### Shorthands

shorthand | meaning |
---|---|

iff | if and only if |

$\therefore$ | therefore |

$\approx$ | approximately |

$ab$ | $a$ * $b$ |

$a(b)$ | $a$ * $b$ |

$|a|$ | absolute value of $a$ |

$\lceil{a}\rceil$ | ceiling, round $a$ up to next biggest whole number. Example: $\lceil{2.3}\rceil = 3$ |

$\lfloor{a}\rfloor$ | floor, round $a$ down to the next smallest whole number. Example: $\lfloor{2.9}\rfloor = 2$ |

### Variables

In math, like programming, we use variables. Variables can take on some numeric value and we use it as a short hand in a mathematical expression. Before using a variable, you should define what it means (like declaring a variable in a program)

For example:

"Let n represent the size of an array"

This means that the variable n is a shorthand for the size of an array in later statements.

### Functions

Similar to functions in programming, mathematics have a notation for functions. Mathematically speaking, a function has a single result for a given set of arguments. When writing out mathematical proof, we need to use the language of math which has its own syntax

As a function works with some argument, we first define what the arguments mean then what the function represents.

#### For example:

Let $n$ represent the size of the array (n is the name of the argument) Let $T(n)$ represent the number of operations needed to sort the array

We pronounce $T(n)$ as "T at n". Later we will assoicate $T(n)$ with a mathematical expression that we can use to make some calculation. The expression will be a mathematical statement that can be used to calculate the number of operations needed to sort the array. If we supply the number 5, then $T(5)$ would be the number of operations needed to sort an array of size 5

#### Summary

$T(n)$ - read it as T at n, we call the function T.

$T(n) = {n^2} + n + 2$ means that $T(n)$ is the same as the mathematical expression ${n^2} + n + 2$

n can take on any value (unless there are stated limitations) and result of a function given a specific value is calculated simply by replacing n with the value

$T(5) = {5^2} + 5 + 2 = 32$ ( we pronounce $T(5)$ as "T at 5")

Note that when we talk about big-O notation (and related little-o, theta and omega notation) those are not functions (though it kind of looks like it)

### Sigma Notation

Sigma notation is a shorthand for showing a sum. It is similar in nature to a for loop in programming.

#### General summation notation.

$\sum\limits_{i=1}^{n} t_i = t_1 + t_2+ ... + t_n$

The above notation means that there are n terms and the summation notation adds each of them together.

Typically the terms $t_i$ is some sort of mathetmatical expression in terms of i (think of it as a calculation you make with the loop counter). the i is replaced with every value from the initial value of i (at the bottom of the $\sum$) going up by 1 to n (the value at the top of the $\sum$)

#### Example:

$\sum\limits_{i=1}^{5} i = 1 + 2 + 3 + 4 + 5$

## Mathematical Definitions and Identities

Mathematical identities are expressions that are equivalent to each other. Thus, if you have a particular term, you can replace it with its mathematical identity.

### Exponents

##### definition

${x^n}$ means $(x)(x)(x)...(x)$ ($n$ $x$'s multiplied together)

##### identities

${x^ax^b}={x^{a+b}}$

$\frac{x^a}{x^b} = {x^{a-b}}$

${({x^a})^b} = {x^{ab}}$

${x^a}+{x^a} = 2{x^a} \neq {x^{2a}}$

${2^a}+{2^a} = 2({2^a}) = {2^{a+1}}$

### Logarithms

In computer text books, unless otherwise stated $log$ means $log_2$ as opposed to $log_{10}$ like math text books

##### definition

${b^n} = a$ *iff* $log_ba = n$ In otherwords $log_ba$ is the exponent you need to raise b by in order to get a.

##### identities

$\log_ba = \frac{\log_ca}{\log_cb}$, where $c > 0$

$\log {ab} = \log a + \log b$

$\log (\frac{a}{b}) = \log a - \log b$

$\log {a^b} = {b}{\log a}$

$\log x < x$ for all $x > 0$

$\log 1 = 0$

$\log 2 = 1$

### Series

A series is the sum of a sequence of values. We usually express this using sigma notation (see above).

#### identities

$\sum\limits_{i=0}^{n} c(f(i)) = c \sum\limits_{i=0}^{n}f(i)$, where $c$ is a constant

$\sum\limits_{i=0}^{n} {2^i} = {2^{n+1}} - 1$

$\sum\limits_{i=0}^{n} {a^i} = \frac{a^{n+1}- 1}{ a - 1}$

$\sum\limits_{i=0}^{n} {a^i} \leq \frac{1}{a-1}$ if $0 < a < 1$

$\sum\limits_{i=1}^{n} {i} = \frac{n(n+1)}{2}$

$\sum\limits_{i=1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6}$

$\sum\limits_{i=1}^{n}{f(n)} = nf(n)$

$\sum\limits_{i=n_0}^{n} f(i) = \sum\limits_{i=1}^{n} f(i) - \sum\limits_{i=1}^{n_0 - 1} f(i)$