Complexity Analysis Formula Sheet

Math for CS · Axiom Academy

Asymptotic Notation Definitions f(n) = O(g(n)) : There exist c > 0, n_0 such that for all . (Upper bound) : There exist c > 0, n_0 such that for all . (Lower bound) : f(n) = O(g(n)) and . (Tight bound) f(n) = o(g(n)) : . (Strictly smaller) Geometric series: . For r > 1 : . For r < 1 : . Stirling's approximation: , so P: Decidable in polynomial time by a deterministic TM NP: Verifiable in polynomial time (or solvable by a nondeterministic TM) NP-hard: Every NP problem reduces to it in polynomial time NP-complete: In NP and NP-hard co-NP: Complement of NP problems (can verify "no" answers in poly time)

This is the written version of the interactive lesson above. See the full Math for CS course.