Mathematical Foundations of Algorithm Analysis

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

Asymptotic Running Time of an Algorithm

Asymptotic Running Times - Example

• Add two n-digit numbers. (With pencil and paper, of course.)
• Multiply two n-digit numbers. (Also with pencil and paper.)

Asymptotic Notations

• O-notation: for asymptotic upper bounds
• Omega-notation: for asymptotic lower bounds
• Theta-notation: for asymptotically tight bounds

O-notation

• O(g(n)) = { f(n): there exist positive constants c and n₀ such that 0 <= f(n) <= c*g(n) for all n>=n₀ }
• O(g(n)) = { functions that grow asymptotically slower than g(n) }
• 100n³ + 50n² + 60n = O(n³)
• 100n³ + 50n² + 60n = O(2ⁿ)
• 100n³ + 50n² + 60n != O(n²)
• 2ⁿ = O(3ⁿ)

Omega-notation

• Omega(g(n)) = { f(n): there exist positive constants c and n₀ such that 0 <= c*g(n) <= f(n) for all n>=n₀ }
• Omega(g(n)) = { functions that grow asymptotically faster than g(n) }
• n² log n = Omega(n²)

Theta-notation

• Theta(g(n)) = { f(n): there exist positive constants c₁, c₂, n₀ such that 0 <= c₁*g(n) <= f(n) <= c₂*g(n) for all n>=n₀ }
• Theta(g(n)) = { functions that grow asymptotically as fast as g(n)) }
• (4n + sin n)*(5n - cos n) = 20n² + O(n) = Theta(n²)

Examples

• 3n² + 6n + 17 = Theta(n²)= O(n²) = Omega(n²)
• 3n² + 6n + 17 = O(n⁹)
• 3n² + 6n + 17 = Omega(n log n)
• 2ⁿ⁺¹ = Theta(2ⁿ)
• 2²ⁿ = Omega(2ⁿ)

Exercise

• (sqrt(2))^{log n}
• n²
• n!
• 2²ⁿ⁺¹
• 1.5ⁿ
• n³
• log²n
• log (n!)
• 2²ⁿ
• n^{1/(log n)}
• ln ln n
• n * 2ⁿ
• n^{log log n}
• ln n
• 1
• 2^{log n}
• (log n)^{log n}
• eⁿ
• 4^{log n}
• (n+1)!
• sqrt(log n)
• n log n
• n
• 2ⁿ

Recurrences

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(n²)   (Is this still O(n²)?)

Solving Recurrences

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

• 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

Expanding a Recurrence

• 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)ⁱ from 0 to oo)
• T(n) = 3n
• T(n) = Theta(n)

Visualize the Recursion Tree

• 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

• If f(n) is smaller than n^log_ba, then T(n) = Theta(n^log_ba).
• If f(n) and n^log_ba are the same, then T(n) = Theta(n^log_ba log n).
• If f(n) is larger than n^log_ba, then T(n) = Theta(f(n)).

Multiplication revisited

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

Elements of Discrete Mathematics

• 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

• 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 (v₀,v₁,..., v_k-1,v_k) where all (v_i,v_i+1 are edges of the graph is called a path of length k that connects the vertices v₀ and v_k.
• 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 (v₀,v₁,..., v_k-1,v_k) forms a cycle, if v₀ = v_k 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.

Last modified 2001-01-29