Proof by diagonalization that there are uncomputable functions; introduction to complexity theory, big-Oh notation, definition of worst-case for a non-deterministic. Turing machine; definition of the classes P and NP.