Что такое space complexity?

Space complexity — сколько дополнительной памяти использует алгоритм в зависимости от размера входа. O(1) — константная память (in-place сортировка, two pointers). O(n) — линейная (создание копии массива, хеш-таблица). O(log n) — стек рекурсии при бинарном поиске. MergeSort требует O(n) доп. памяти, QuickSort — O(log n) на стек. В Go важно помнить: slice header — 24 байта, но underlying array может быть огромным. map потребляет значительно больше памяти, чем slice для тех же данных.