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. Where possible analogies between mathematical and programming concepts are drawn

Mathematical Notations and Shorthands

Shorthands

shorthand

meaning

iff

if and only if

\therefore

therefore

\approx

approximately

abab

a * b

a(b)a(b)

a * b

$$

a

$$

absolute value of a

a\lceil{a}\rceil

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

a\lfloor{a}\rfloor

floor, round aa down to the next smallest whole number. Example: 2.9=2\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 nn represent the size of the array - (n is the name of the argument).

Let T(n)T(n) represent the number of operations needed to sort the array - T is the name of the function, and it accepts a single variable nn

We pronounce T(n)T(n) as "T at n". Later we will assoicate T(n)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)T(5) would be the number of operations needed to sort an array of size 5

Summary

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

T(n)=n2+n+2T(n) = {n^2} + n + 2 means that T(n)T(n) is the same as the mathematical expression n2+n+2{n^2} + n + 2. Think of T(n)T(n) as being like the function prototype, and n2+n+2{n^2} + n + 2 as being like the function definition

nn 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)=52+5+2=32T(5) = {5^2} + 5 + 2 = 32 ( we pronounce T(5) as "T at 5")

When we talk about big-O notation (and related little-o, theta and omega notation) those are NOT functions. For example O(n) is NOT a function named O that takes a variable n. It's meaning is different.

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.

i=1nti=t1+t2+...+tn\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 tit_i,​​ is some sort of mathematical expression in terms of ii (think of it as a calculation you make with the loop counter). The ii is replaced with every value from the initial value of 1 (at the bottom of the \sum ), going up by 1, to n (the value at the top of the \sum∑)

Example:

i=15i=1+2+3+4+5\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

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

Identities

xaxb=xa+b{x^ax^b}={x^{a+b}}

xaxb=xab\frac{x^a}{x^b} = {x^{a-b}}​

(xa)b=xab{({x^a})^b} = {x^{ab}}

xa+xa=2xax2a{x^a}+{x^a} = 2{x^a} \neq {x^{2a}}

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

Logarithms

In computer text books, unless otherwise stated loglog means log2log_2 ​​ as opposed to log10log_{10} ​​ like math text books

Definition

bn=a{b^n} = a iff logba=nlog_ba = n In otherwords logbalog_ba is the exponent you need to raise bb by in order to get aa

Identities

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

logab=loga+logb\log {ab} = \log a + \log b

log(ab)=logalogb\log (\frac{a}{b}) = \log a - \log b

logab=bloga\log {a^b} = {b}{\log a}

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

log1=0\log 1 = 0

log2=1\log 2 = 1

Series

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

Identities

i=0nc(f(i))=ci=0nf(i)\sum\limits_{i=0}^{n} c(f(i)) = c \sum\limits_{i=0}^{n}f(i) ​, where cc is a constant

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

i=0nai=an+11a1\sum\limits_{i=0}^{n} {a^i} = \frac{a^{n+1}- 1}{ a - 1}​

i=0nai1a1\sum\limits_{i=0}^{n} {a^i} \leq \frac{1}{a-1}

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

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

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

i=n0nf(i)=i=1nf(i)i=1n01f(i)\sum\limits_{i=n_0}^{n} f(i) = \sum\limits_{i=1}^{n} f(i) - \sum\limits_{i=1}^{n_0 - 1} f(i)

Last updated