Algorithm/Structure Complexity: The runtime complexity for one data structure / algo

Problem Complexity: Choosing the most efficient algo/structure.

• Upper bound: Give an example of an algo that runs in that upper bound
• Lower bound: Prove that no algos run faster than that lower bound (hard)
  • Argue based on computational models

Comparison Trees (Lower Bound)

• Represent algorithms whose main ops are comparisons
• For every input size n, list all comparisons in a tree
  • Internal nodes: 1 comparison Children/Edges: Results of comparisons Leaves: Outcome of the entire algo
• Each algo generates a family of comparison trees (e.g. binary search)
• Runtime of algo ∈ θ(#comparisons) ∈ θ(comparison tree height)
• Min height = lower bound on every comparison-based algorithm.
• The comparison tree must have one leaf for each possible outcome (e.g. #leaves ≥ n+1 for binary search returning an index)
• If each comparison is a 2-way comparison, height ≥ log2(#nodes) ≥ log2(#leaves) (e.g. every searching algorithm takes Ω(log n))

Example: Sorting

Input: List A (length n)

Outcome: Permutation of [0, 1, …, n-1] for indices of the sorted list

Lower bound proof:

• #outcomes = n! (possible permutations)
• #leaves ≥ n!
• worst-case #comparisons ≥ min height ≥ log(n!) = Ω(n log n)