Die Theoretische Informatik beschäftigt sich mit den theoretischen Grundlagen der Informatik. Zwei Kerngebiete sind die Komplexitätstheorie und die Algorithmik. Forschende im Bereich der Komplexitätstheorie stellen sich die Frage, welche Probleme sich wie effizient lösen lassen. Basierend auf einem formalen Rechenmodell ergeben sich dabei Klassen von Problemen verschiedener Komplexität. Die Komplexitätstheorie untersucht, wie sich diese Klassen zueinander verhalten.
In der Algorithmik werden Methoden zum Entwurf und der Analyse effizienter Algorithmen betrachtet. Die beiden Gebiete, Algorithmen und Komplexität, hängen eng miteinander zusammen. Auch sind Algorithmen eng verknüpft mit Datenstrukturen, da manche effiziente Algorithmen geschickte Datenstrukturen benötigen. Datenstrukturen hingegen benötigen geschickte Algorithmen zur Konstruktion, Modifikation und Abfrage.