Introduction to computational complexity theory

Execution time is a key element for most algorithms, especially in combinatorial problems, optimization, calculation or database management. Computational complexity theory arose to study and compare running time of algorithms. We will introduce basic theoretical concepts to assess the speed of algorithms like Turing machines, evaluate complexity \(( O(n), O(n\> \text{log}(n)), O(n^2), ... )\) of classical examples such as sorting algorithms and discuss notions of NP-complexity (P, NP, NP-Hard, NP-Complete, ...).