brycewang-stanford Algorithms and Complexity Guide
A skill for analyzing algorithm complexity and computational efficiency in research contexts. Covers asymptotic notation, common complexity classes, NP-completeness, amortized analysis, and strategies for presenting algorithmic contributions in papers.
Asymptotic Notation
Big-O, Omega, and Theta
O(f(n)) -- Upper bound (worst case, "at most")
T(n) is O(f(n)) if T(n) <= c * f(n) for large n
Omega(f(n)) -- Lower bound (best case, "at least")
T(n) is Omega(f(n)) if T(n) >= c * f(n) for large n
Theta(f(n)) -- Tight bound (exact asymptotic growth)
Both O(f(n)) and Omega(f(n))
Common growth rates (slowest to fastest):
O(1) < O(log n) < O(sqrt(n)) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
Practical Interpretation
def estimate_runtime(n: int, complexity: str) -> dict:
"""
Estimate practical runtime for common complexities.
Args:
n: Input size
complexity: Complexity class string
"""
import math
complexities = {
"O(1)": 1,
"O(log n)": math.log2(max(n, 1)),
"O(n)": n,
"O(n log n)": n * math.log2(max(n, 1)),
"O(n^2)": n ** 2,
"O(n^3)": n ** 3,
"O(2^n)": 2 ** min(n, 40), # Cap to avoid overflow
}
operations = complexities.get(complexity, n)
# Assuming ~10^9 operations per second
seconds = operations / 1e9
return {
"input_size": n,
"complexity": complexity,
"estimated_operations": operations,
"estimated_time": (
f"{seconds:.2e} seconds"
if seconds < 60
else f"{seconds / 60:.1f} minutes"
if seconds < 3600
else f"{seconds / 3600:.1f} hours"
),
"feasible": operations < 1e12 # Roughly 1000 seconds
}
Complexity Classes
P, NP, and Beyond
P: Problems solvable in polynomial time
Examples: Sorting, shortest path, MST, linear programming
NP: Problems verifiable in polynomial time
(Given a solution, can check it quickly)
Examples: SAT, TSP, graph coloring, subset sum
NP-Complete: The "hardest" problems in NP
If any one is in P, then P = NP
Proven via reduction from a known NP-complete problem
NP-Hard: At least as hard as NP-complete
Not necessarily in NP (may not even be decision problems)
Examples: Optimization versions of NP-complete problems
PSPACE: Solvable with polynomial space (possibly exponential time)
Examples: QBF, certain game-theoretic problems
Proving NP-Completeness
To prove problem X is NP-complete:
1. Show X is in NP:
- Given a certificate (proposed solution), verify it in poly time
2. Reduce a known NP-complete problem Y to X:
- Construct a polynomial-time transformation f
such that Y has solution iff f(Y) has solution in X
- Common starting problems: SAT, 3-SAT, Vertex Cover,
Hamiltonian Path, Subset Sum
Algorithm Analysis Techniques
Recurrence Relations
For divide-and-conquer algorithms, solve recurrences:
Master Theorem: T(n) = a * T(n/b) + O(n^d)
Case 1: d < log_b(a) -> T(n) = O(n^(log_b(a)))
Case 2: d = log_b(a) -> T(n) = O(n^d * log n)
Case 3: d > log_b(a) -> T(n) = O(n^d)
Examples:
Merge Sort: T(n) = 2T(n/2) + O(n) -> O(n log n) [Case 2]
Binary Search: T(n) = T(n/2) + O(1) -> O(log n) [Case 2]
Strassen: T(n) = 7T(n/2) + O(n^2) -> O(n^2.81) [Case 1]
Amortized Analysis
Amortized analysis provides the average cost per operation over
a worst-case sequence of operations.
Methods:
- Aggregate method: Total cost / number of operations
- Accounting method: Assign "credits" to cheap operations
- Potential method: Define a potential function
Example: Dynamic array (ArrayList)
Most insertions: O(1)
Occasional resize: O(n)
Amortized cost per insertion: O(1)
(The expensive resizes are rare enough that the average stays constant)
Presenting Algorithms in Papers
Algorithm Pseudocode Standards
% Use the algorithm2e or algorithmicx package in LaTeX
\begin{algorithm}[H]
\caption{Description of Algorithm}
\label{alg:myalgorithm}
\KwIn{Input description}
\KwOut{Output description}
initialization\;
\While{condition}{
compute something\;
\If{condition}{
action\;
}
}
\Return result\;
\end{algorithm}
What to Include in an Algorithms Paper
1. Problem definition (formal, with input/output specification)
2. Related work and existing approaches with their complexities
3. Algorithm description (pseudocode + English explanation)
4. Correctness proof (invariants, termination argument)
5. Complexity analysis (time and space, worst/average/amortized)
6. Experimental evaluation:
- Comparison with baselines on standard benchmarks
- Runtime scaling with input size (empirical vs. theoretical)
- Real-world datasets in addition to synthetic ones
7. Discussion of practical considerations (constants, cache behavior)
Dealing with Intractability
When you encounter NP-hard problems in your research, consider: polynomial-time approximation algorithms (with provable approximation ratios), heuristics (greedy, local search, simulated annealing), fixed-parameter tractable (FPT) algorithms if a relevant parameter is small, integer linear programming (ILP) solvers for moderate-size instances, or restricting to special cases where the problem becomes tractable (e.g., trees, planar graphs).