Complessità spaziale

Misura di quanta memoria aggiuntiva un algoritmo richiede in funzione della dimensione dell'input. È spesso in compromesso con la complessità temporale: risparmiare tempo può costare spazio e viceversa.