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
abab aa * bb
a(b)a(b) aa * bb
a |a| absolute value of aa
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

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

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

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

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 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:

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) (nn xx'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 b by in order to get a.

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>0 x > 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} if 0<a<1 0 < 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)

results matching ""

    No results matching ""