Space Complexity

overview

Summary

Space complexity measures total memory_usage of an algorithm as a function of input_size. It includes input storage and auxiliary_space. We describe it with big_o for an upper bound, plus big_theta and big_omega when needed. An in_place algorithm uses O(1) auxiliary space. Recursion adds a recursion_stack proportional to call depth. Arrays and hash maps typically use O(n) space. Report worst_case, average_case, and best_case when relevant. Compare space needs across algorithms using the same model.