Mathematical Foundations of Algorithm Analysis

## Mathematical Foundations of Algorithm Analysis

a WimpyPoint presentation owned by Mark Dettinger

## Mathematical Foundations of Algorithm Analysis

• Asymptotic Running Times
• Solving Recurrences
• Elements of Discrete Mathematics
```

```

## Asymptotic Running Time of an Algorithm

When we analyze the running time of an algorithm, it's usually not worth to compute the exact running time. For large input sizes only the order of growth of the running time - the asymptotic running time - is relevant.
Most times it does not matter if an algorithm is 2, 3 or 10 times faster than an other algorithm. Constant factors are dwarfed by the effect of the input size.

The real question to ask when we analzye an algorithm's efficieny is: If we double the input size, how does this affect the running time of the program? Does it run twice as long? Or four times as long? Or even longer?

```

```

## Asymptotic Running Times - Example

Which one is the more tedious job? (You will be told the value of n after accepting the assignment.)
• Add two n-digit numbers. (With pencil and paper, of course.)
• Multiply two n-digit numbers. (Also with pencil and paper.)
Adding two n-digit numbers takes time proportional to n.
Multiplying two n-digit numbers takes time proportional to n2.
```

```

## Asymptotic Notations

When we talk about the running time of an algorithm, we use three different notations to give upper, lower or tight bounds of the asymptotic running time.
• O-notation: for asymptotic upper bounds
• Omega-notation: for asymptotic lower bounds
• Theta-notation: for asymptotically tight bounds
```

```

## O-notation

For asymptotic upper bounds.
• O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n>=n0 }
• O(g(n)) = { functions that grow asymptotically slower than g(n) }
• 100n3 + 50n2 + 60n = O(n3)
• 100n3 + 50n2 + 60n = O(2n)
• 100n3 + 50n2 + 60n != O(n2)
• 2n = O(3n)
```

```

## Omega-notation

For asymptotic lower bounds.
• Omega(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n>=n0 }
• Omega(g(n)) = { functions that grow asymptotically faster than g(n) }
• n2 log n = Omega(n2)
```

```

## Theta-notation

For asymptotically tight bounds.
• Theta(g(n)) = { f(n): there exist positive constants c1, c2, n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n>=n0 }
• Theta(g(n)) = { functions that grow asymptotically as fast as g(n)) }
• (4n + sin n)*(5n - cos n) = 20n2 + O(n) = Theta(n2)
```

```

## Examples

• 3n2 + 6n + 17 = Theta(n2)= O(n2) = Omega(n2)
• 3n2 + 6n + 17 = O(n9)
• 3n2 + 6n + 17 = Omega(n log n)
• 2n+1 = Theta(2n)
• 22n = Omega(2n)
Quiz question: Why doesn't it make sense to say: "The running time of this algorithm is at least O(n2)"
```

```

## Exercise

Rank the following functions by order of growth.
• (sqrt(2))log n
• n2
• n!
• 22n+1
• 1.5n
• n3
• log2n
• log (n!)
• 22n
• n1/(log n)
• ln ln n
• n * 2n
• nlog log n
• ln n
• 1
• 2log n
• (log n)log n
• en
• 4log n
• (n+1)!
• sqrt(log n)
• n log n
• n
• 2n
```

```

## Recurrences

When an algorithm contains a recursive call, its running time can often be described by a recurrence.

#### Examples

• T(n) = n + T(n-1)                (Maxsort)
• T(n) = 2 T(n/2) + O(n)       (Mergesort)
• T(n) = T(n/2) + O(n)          (Finding the kth-largest element in a list)
• T(n) = 20 T(n/5) + O(n2)   (Is this still O(n2)?)
How do you solve such a recurrence equation?
```

```

## Solving Recurrences

Four common ways to solve a recurrence are:
• Guess the solution, then use induction to prove it.
• Expand the recurrence and convert it into a summation.
• Visualize the recursion tree.
• Use the master theorem.
```

```

## Guess the solution and then prove it.

T(n) = 2 T(n/2) + n
• We guess the solution is T(n) = Theta(n log n)
• Prove that T(n) <= cn log n for some constant c>0.
• T(n) <= 2 (c n/2 log n/2) + n
• = cn log n/2 + n
• = cn (log n - log 2) + n
• = cn log n - cn + n
• <= cn log n
• QED
The last step holds for c>=1.
```

```

## Expanding a Recurrence

Doesn't require you to guess the solution, but it may require more algebra than guessing and then proving it by induction.
• T(n) = n + 2 T(n/3)
• T(n) = n + 2 (n/3 + 2 T(n/9))
• T(n) = n + 2 (n/3 + 2 (n/9 + 2 T(n/27)))
• T(n) = n + 2/3 n + 4/9 n + 8/27 n + 16/81 n + ...
• T(n) = n (1 + 2/3 + 4/9 + 8/27 + 16/81 + ...)
• T(n) = n * (Sum (2/3)i from 0 to oo)
• T(n) = 3n
• T(n) = Theta(n)
```

```

## Visualize the Recursion Tree

T(n) = 2 T(n/2) + n2
• Draw the recursion tree.
• Label each node with its cost.
• Compute the cost of each level of the tree.
• Compute the total cost of all levels.
```

```

## The Master Theorem

To solve the recurrence T(n) = a T(n/b) + f(n), compare f(n) with nlogba.
• If f(n) is smaller than nlogba, then T(n) = Theta(nlogba).
• If f(n) and nlogba are the same, then T(n) = Theta(nlogba log n).
• If f(n) is larger than nlogba, then T(n) = Theta(f(n)).
This is a rather sloppy definition, but it is good enough for most functions that we will encounter. There are some more technical formalities that should be understood, however. They are explained in "Cormen, Leiserson, Rivest: Introduction to Algorithms", pages 62-63.
```

```

## Multiplication revisited

• Multiplying two n-digit numbers takes O(n2) time.
• At least if you use the algorithm that is taught in elementary school.
• But is there a better way?
```

```

## Elements of Discrete Mathematics

We review the notations, definitions and elementary properties of the elements of discrete mathematics that are most relevant for the Algorithms course.
• Sets
• Relations
• Functions
• Graphs
• Trees
```

```

## Sets, Relations, Functions

• A set is a collection of distinguishable objects.
• A binary relation on two sets A and B is a subset of the Cartesian product A x B.
Example: the "less than" relation on natural numbers is the set { (1,2), (1,3), (2,3), (1,4), (2,4),...) }
• Formally, a function f is a binary relation on A x B such that for all elements of A there is exactly one element of B such that (a,b) is in f.
• Intuitively, a function is a mapping that assigns an element of B to each element of A.
```

```

## Graphs

• Formally, a graph is a pair (V,E) where V is a finite set and E is a binary relation on V.
• Intuitively, a graph is a network consisting of vertices (V) and edges (E) that connect the vertices.
• The edges can be directed or undirected. Dependent on that, the resulting graph is called a directed graph or an undirected graph.
• By convention, edges from a vertex to itself - self-loops - are allowed in directed graphs, but forbidden in undirected graphs..
• A directed graph without self-loops is called simple.
• If (u,v) is an edge of a directed graph, we say that (u,v) leaves u and enters v.
• If (u,v) is an edge of a graph, we say that u and v are adjacent to each other.
• The degree of a vertex is the number of edges incident on it.
• In case of a directed graph, the in-degree of a vertex is the number of edges entering it, the out-degree is the number of edges leaving it, and its degree is the sum of its in-degree and out-degree.
```

```

## Example Graph Problem: The Party Problem

Is it possible that at a party with at least 6 people the following two conditions can both guaranteed?
• If you select 3 people randomly, at least two of them should already know each other.
• If you select 3 people randomly, at least two of them should not know each other.
```

```

## Graphs - Paths and Cycles

• A sequence of vertices (v0,v1,..., vk-1,vk) where all (vi,vi+1 are edges of the graph is called a path of length k that connects the vertices v0 and vk.
• If there is a path p from u to v, we say that v is reachable from u via p.
• A path is simple, if all vertices in the path are distinct.
• A path (v0,v1,..., vk-1,vk) forms a cycle, if v0 = vk and the path contains at least one edge.
• An undirected graph is connected, if every pair of vertices is connected by a path.
• A directed graph is strongly connected, if every two vertices are reachable from each other.
```

```

## Graph Problems

• Euler Circuit: find a cycle in a graph that visits each edge exactly once.
• Hamiltonian Circuit: find a cycle in a graph that visits each vertex exactly once.
• Determine the strongly connected components in a directed graph.
• Test if two graphs are isomorphic.
```

```

## Trees

• An undirected, acyclic, connected graph is called a tree.
• An undirected, acyclic, but possibly disconnected graph is called a forest.
• Any two vertices in a tree are connected by a unique simple path.
• A tree with n nodes has n-1 edges.
• If any edge is removed from a tree, the resulting graph is a forest of two trees.
• If any edge is added to a tree, the resulting graph contains a cycle.
```

```