La complexité spatiale mesure la quantité de mémoire supplémentaire qu'un algorithme utilise en fonction de la taille de l'entrée, sans compter l'entrée elle-même. Elle s'exprime en notation grand O et s'arbitre souvent contre la complexité temporelle : on peut gagner du temps en stockant plus de résultats.
Exemple
Inverser une liste en créant une copie utilise O(n) de mémoire ; l'inverser sur place en utilise O(1).