Mathematical logic
Set theory
Order theory
Formal language theory
Enumerative combinatorics
Automata theory

Real analysis (Big-O notation)


\chapter{Time complexity}


Naturally, DFA run in $O(n)$

P-complete
P-hard
NP-complete
NP-hard

3-SAT problem
Cook-Levin theorem


P
NP



\chapter{Space complexity}

Savitch's theorem