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

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