Space Complexity

Math for CS · Axiom Academy

Memory usage, in-place algorithms, and space-time tradeoffs Time complexity measures how many operations an algorithm performs. Space complexity measures how much memory it uses, as a function of input size . Definition: The space complexity of an algorithm is the total amount of memory it requires, expressed as a function of the input size. We typically measure auxiliary space — the extra memory beyond the input itself. Why does this matter? Memory is finite. An algorithm that sorts a 10 GB file needs to fit in RAM (or use disk cleverly). Embedded systems may have only kilobytes. Mobile apps must be memory-efficient to avoid being killed by the OS. Total space: Input + auxiliary memory. For an array of elements, at least . Auxiliary space: Extra memory beyond the input. This is the more useful measure — it tells you how much additional memory the algorithm needs. An in-place algorithm uses only a constant amount of auxiliary space: extra memory. It transforms the input using the input's own storage, without allocating significant additional data structures. Examples of in-place algorithms: Selection sort: Scans for the minimum, swaps it to the front. Auxiliary space: (just a few variables). Insertion sort: Shifts elements within the array. Auxiliary space: . Heap sort: Builds a max-heap in the array, then extracts. Auxiliary space: . Quicksort: Partitions in-place. Auxiliary space: for the recursion stack (best/average case).

This is the written version of the interactive lesson above. See the full Math for CS course.