Space complexity
Space complexity describes how much additional memory an algorithm needs as its input grows. This includes temporary collections, stored results, links between nodes, and the call stack used by recursive functions.
After checking runtime in Time complexity, inspect what the help desk stores in addition to the tickets themselves. The dictionary, event set, queues, action history, and graph all consume memory because they preserve different rules.
Examples
- A few variables use
O(1)additional space. - A second collection containing one item for every input item uses
O(n)space. - A recursive traversal may use space proportional to the depth of the structure.
Time and memory trade-offs
Sometimes a program uses more memory to reduce running time. A dictionary or set may store extra information so that lookup or membership checks are fast. That trade-off is useful only when the memory is available and the faster operation matters.
When evaluating a design, ask whether the stated space is additional space or the memory already required to store the input. Also consider peak usage, because temporary data can matter even if it is released later.
For this case study, a graph’s adjacency lists grow with its vertices and edges, while a scan that uses only a few variables may use O(1) additional space. The input storage and the extra index should be counted separately.
Memory is part of the trade-off whenever a faster operation needs an additional index or collection.