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
|iff||if and only if|
|absolute value of|
|ceiling, round up to next biggest whole number. Example:|
|floor, round down to the next smallest whole number. Example:|
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)
"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.
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.
Let represent the size of the array (n is the name of the argument) Let represent the number of operations needed to sort the array
We pronounce as "T at n". Later we will assoicate 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 would be the number of operations needed to sort an array of size 5
- read it as T at n, we call the function T.
means that is the same as the mathematical expression
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
( we pronounce 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 is a shorthand for showing a sum. It is similar in nature to a for loop in programming.
General summation notation.
The above notation means that there are n terms and the summation notation adds each of them together.
Typically the terms 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 ) going up by 1 to n (the value at the top of the )
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.
means ( 's multiplied together)
In computer text books, unless otherwise stated means as opposed to like math text books
iff In otherwords is the exponent you need to raise b by in order to get a.
A series is the sum of a sequence of values. We usually express this using sigma notation (see above).
, where is a constant