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