Appendix: Mathematics Review
Last updated
Last updated
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
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.
For example:
Summary
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 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.
Example:
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.
A series is the sum of a sequence of values. We usually express this using sigma notation (see above).
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 - T is the name of the function, and it accepts a single variable
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 .
means that is the same as the mathematical expression . Think of as being like the function prototype, and as being like the function definition
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 T(5) as "T at 5")
Typically the terms , is some sort of mathematical expression in terms of (think of it as a calculation you make with the loop counter). The is replaced with every value from the initial value of 1 (at the bottom of the ), going up by 1, to n (the value at the top of the \sum∑)
means (n x'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 by in order to get
, where
for all
, where is a constant
shorthand
meaning
iff
if and only if
therefore
approximately
a * b
a * b
absolute value of a
ceiling, round aa up to next biggest whole number. Example:
floor, round aa down to the next smallest whole number. Example: