Pamięciowa złożoność obliczeniowa Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć maszyny abstrakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej wyrażonej w bitach lub bajtach.
Porównywanie złożoności algorytmów Porównując złożoność algorytmów, bierze się pod uwagę asymptotyczne tempo wzrostu, czyli to jak zachowuje się funkcja określająca złożoność dla odpowiednio dużych, granicznych argumentów (rozmiarów danych wejściowych), ignorując zachowanie dla małych danych. Ponadto złożoności algorytmów różniące się o stałą uważa się za takie same, co eliminuje wpływ szybkości działania komputera, na którym dany algorytm ma być wykonany, oraz wybór operacji podstawowej, która na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zastąpiona szeregiem instrukcji.