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):