complexity theory is a theory in algorithms to analyze time classes. older Notes We know that O(n\ log\ n) is between O(n) and O(n^2) — so we can roughly call it “polynomial time.” Since the optimal comparison cannot be faster than polynomial time, we say that comparison-based sorting is a polynomial-time algorithm. From this information, we can come up with two main time classes: P for solutions with known polynomial time, NP for non-deterministic polynomial time. Think of it as P is solvable with polynomial time and NP is verifiable with polynomial time. The cool thing about NP problems is that solving a subset of them ("NP hard" problems) solves all NP problems. reduction (algorithms) reduction is how you can use NP-hard problems to solve all NP problems in complexity theory. Say, multiplication: say you have a basic algorithm to add we can perform multiplication by asking our black box addition algorithm to add n times in complexity theory terms, this means addition is “at least as hard” as multiplication. Because, if we can solve any addition problem, we can solve any multiplication problem. “Given this, do that.” problem classes (see above) “Polynomial time” P — problems solvable with polynomial time “Non-deterministic polynomial time” NP — problem verifiable with polynomial time “Exponential time” EXPTIME — problems that can only be solved in exponential time “2 Exponential time” 2EXPTIME — class of problems that takes 2^{2^n} time to solve Space complexity works in a similar way. P and NP are deterministic and non-deterministic in context to a Turing machine. Fundamentally, P and NP only apply to decision problems—given a problem, output “yes” or “no.” However, this definition can be stretched: sorting is a decision problem, because it can be stated as “given an unsorted array, can you verify whether or not an array is sorted”