Unter der
Platzkomplexität eines Problems versteht man den (minimalen) Bedarf an Speicherplatz eines
Algorithmus zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe. Es interessiert also nicht der Speicherbedarf eines konkreten
Programms auf einem bestimmten Computer, sondern vielmehr,
wie der Speicheraufwand wächst, wenn mehr Daten zu verarbeiten sind. Beispielsweise beantwortet die Platzkomplexität die Frage, ob sich der benötigte Speicher bei doppelter Eingabe-Datenmenge verdoppelt oder quadriert (siehe auch
Skalierbarkeit). Sie wird deshalb auch
Speicherkomplexität genannt.