Mathematical Background for Algorithm Analysis

In order to deal with the mathematical aspects of algorithm analysis, we need to be sure we have a clear grasp of some notational conventions, and that we understand a few basic principles and formulas.

Interval Notation

Interval notation is a convenient means of indicating a certain kind of range of values. First let us assume that we have an underlying set of values of some kind (integer, real, even something exotic like C++ STL iterators or Java iterators). The notations shown below assume that a < b (whatever that means in the given context) and should be interpreted to mean, "All values strictly between a and b, and if a square bracket is adjacent to a value, that value is also included, but if a round bracket is next to a value, that value is omitted." That is,

[a, b] means all values between a and b, as well as a and b themselves
(a, b) means all values between a and b (neither a nor b is included)
[a, b) means all values between a and b, with a included, but b not included
(a, b] means all values between a and b, with b included, but a not included

Ranges and Mid-Points

When dealing with algorithms, we are often processing data that is indexed by a range of values, and when doing so we need to be careful not to commit the insidious off-by-one error. In other words, we need to be sure at all times exactly how many values are in the range we are working with.

So, for example, we need to know that the number of values in the closed interval [a, b] with integer end points is b-a+1, while the number of values in the half-open interval [a, b) with integer end points is b-a. These seem to be the two most frequently encountered intervals.

Another operation we perform from time to time is finding the mid-point of an interval with integer end points, and we need to be clear on this procedure. Usually we are doing this because we want the "middle index" between the first and last values in a range of index values. The "middle" value is just the average of the two values, i.e. middle = (first+last)/2, but we need to look closely at what this calculation gives us.

First, note that only if there is an odd number of values in the range do we have a "true" middle value. If we have an even number of values, they split into two equal groups and that puts us in a bit of a dilemma. What value should we choose to be the "middle"? As a matter of convention, when we refer to the "middle" value in a range containing an even number of values, we shall always mean the largest value in the "bottom half" of the range.

Fortunately, the calculation middle = (first+last)/2 gives us the correct value of middle in both cases (i.e., whether the number of values is odd or even), as you can easily convince yourself by looking at a few examples:

middle = (1+10)/2 = 5
middle = (0+9)/2 = 4
middle = (1+11)/2 = 6
middle = (0+10)/2 = 5

Sum and Product Notation

You need to understand the use of

The Σ symbol to indicate summations (used frequently)
The Π symbol to indicate products (used less frequently)

Elementary Functions and the Relative Growth of Such Functions

You need to be thoroughly familiar with the following elementary functions (domain, range, and graph, for example):

Polynomial functions (constant, linear, quadratic, cubic)
Exponential functions (usually base 2)
Logarithmic functions (usually base 2)

The analysis of algorithms involves studying something called the computational complexity of an algorithm to determine how much work the algorithm does in performing its task. This, in turn, requires knowing the order of magnitude of any function we might come up with to express the amount of work done. Since such functions tend to fall into a few common categories (polynomial, logarithmic, exponential, and related functions), it is important to know how these functions relate to each other from the point of view of the "growth" of such a function as its argument increases.

Two Special Useful Functions: The Floor and Ceiling Functions

Often, when we are computing quantities related to the analysis of algorithms, the calculations do not give us "nice" integer answers, which we frequently prefer to have. At the same time, knowing the "nearest integer", sometimes above and sometimes below, the value we have calculated, may be all we need, in the sense of being "close enough". The floor and ceiling functions are useful for finding the nearest integer value, in either direction, to a non-integer value.

The floor function (which, in C++ or Java, is actually called floor and is found in the <cmath> header in C++ and in the Math class is Java) returns the largest integer <= its argument, which may be float, double, or long double. (Mathematicians sometimes call this function the greatest integer function.
The ceiling function (which, in C++ or Java, is called ceil and is also found in the <cmath> header in C++ and in the Math class in Java) returns the smallest integer >= its argument, which may be float, double, or long double.

Methods of Proof

The arguments that we will make in attempting to establish the truth of certain propositions will tend to be more informal than formal. Nevertheless, we may also make use of, and you should certainly be familiar with, a number of the more common and widely used "methods of proof" from your previous mathematical experience. These include

Direct Proof
Show that p implies q implies r implies s implies ...
Examples: Show that if n is odd, then so is the square of n, or if m and n are odd, so is their product.
Indirect Proof (also called Proof by Contrapositive)
Show that p implies q by showing that not-q implies not-p.
Example: Show that if 5n+4 is odd, then so is n.
Proof by Contradiction
Show that not-p implies both q and not-q.
Example: Show that the square root of 2 is irrational.
Proof by Cases
Choose a number of different cases that, taken together, exhaust all possibilities, and prove each one using whatever method is appropriate for that case.
Proof by special technique, such as:
1. Proof by Mathematical Induction
2. Proof by the Pigeonhole Principle
There are also
1. vacuous proofs
2. trivial proofs
3. proofs of equivalence
4. proofs of uniqueness
5. proofs of existence, which may be either constructive or non-constructive

Remember that a single counterexample is sufficient to establish that a general proposition is not true.

Elementary Combinatorics and Factorial Notation

It is often useful to be able to count things. Sometimes we just want to know how many things there are, and that's the end of it. At other times we may want to compare that number with some other number, in order to compute a third quantity, such as a ratio, or a probability, for example. One of the things we often need to count is the number of ways we can "choose r things from n things", where r<=n, and an important distinction to make when doing this is whether or not the order of the r things is important for any reason. If if is, we are counting permutations; if it isn't, we are "merely" counting combinations. In any case, there are a number of useful counting (or combinatorial) principles and formulas that you should know.

Addition Principle: If the number of ways of doing this is m and the number of ways of doing that is n, the number of ways of doing this or that is m+n.
Multiplication Principle: If the number of ways of doing this is m and the number of ways of doing that is n, the number of ways of doing this and that (i.e., doing this followed by doing that) is m*n.
Factorial Notation: n! denotes the product of the first n positive integers. That is,
```
n! = 1 * 2 * 3 * ... * (n-1) * n
```
and note as well that the value of 0! is defined to be 1.
Number of Permutations: The number of permutations of n things taken r at a time is given by this formula:
```
P(n, r) = n!/(n-r)!
```
Number of Combinations: The number of combinations of n things taken r at a time is given by this formula:
```
C(n, r) = n!/((n-r)!r!)
```

Elementary Discrete Probability

Sometimes the analysis of algorithms will require us to compute the probability of an event (also called an outcome), such as the probability that a data element will be found in a certain range of elements, for example. It is therefore useful to have at hand some basic principles of probability calculation and manipulation. The following list is very short and very basic.

Equally Likely Outcomes
If n different things may happen and they are all equally likely, the probability of any particular one of them happening is 1/n, and the probability of any one of a particular group of m of the things happening is m/n.
Certain Probabilities Sum to 1
If a situation is characterized by a group of events that are mutually exclusive (no two of the events can happen simultaneously) and collectively exhaustive (nothing other than one of these events can happen), then the sum of the probabilities of all of these events is 1.
Joint Occurrence of Independent Events
If two events are independent (the occurrence or non-occurrence of either of the events has no effect on the occurrence or non-occurrence of the other), then the probability of both events happening is the product of the individual probabilities. This may be written as follows:
```
P(A and B) = P(A) * P(B)
```
Joint Occurrence of Dependent Events
If two events are dependent (the occurrence of event B, say, is conditional upon the occurrence of the event A), then the probability of both events happening jointly is the probability that A happens multiplied by the probability that B happens, given that A has happened. This may be written as
```
P(A and B) = P(A) * P(B|A)
```
in which P(B|A) is read as "the probability of B, given A" and is called the conditional probability of B, given A.
The probability of the occurrence of one, or the other, or possibly both, of two events, is the sum of their probabilities, minus the probability of both events happening jointly. This may be written as follows:
```
P(A or B) = P(A) + P(B) - P(A and B)
```
A sample space is a collection of all possible events in a particular situation.
A random variable is a function that assigns a real number to each of the events in a sample space, and the distribution of the random variable is a function that maps each value of the random variable to its probability of occurring.
The expectation of a random variable is the sum of the products of each value of the random variable and its corresponding probability.

Miscellaneous Useful Formulas

Sum of First n Positive Integers
```
1 + 2 + 3 + ... + n = n(n+1)/2
```

Sum of Squares of First n Positive Integers

1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6

General Arithmetic Progression:
For the arithmetic progression
```
a, a+d, a+2d, ...
```
the n^th term is given by the formula
```
a_n = a+(n-1)d
```
and the sum of n terms is given by this formula:
```
S_n = n(2a+(n-1)d)/2
```
General Geometric Progression
For the geometric progression
```
a, ar, ar², ... 
```
the n^th term is given by the formula
```
a_n = ar^n-1
```
and the sum of n terms is given by this formula:
```
S_n = a(rⁿ-1)/(r-1)
```
A particular geometric progression: Sum of Powers of 2
```
1 + 2 + 2² + 2³ ... + 2ⁿ = 2ⁿ⁺¹-1
```
Number of Subsets of a Set Containing n Elements: 2ⁿ