Memory usage

An algorithm's memory usage is the storage it occupies under a specified accounting convention. Total storage can include input and output, while auxiliary space complexity counts extra working memory; recursion stacks, temporary arrays and cached results must be included when relevant. An iterative binary search needs constant auxiliary storage, but a recursive implementation can keep logarithmically many stack frames. Reporting $O(n)$ memory without specifying whether $n$ counts bits, elements or machine words can hide a substantial difference. Peak live storage and cumulative allocated storage are also different measurements.

The extra working storage required by an algorithm, excluding the storage occupied by its input. This includes temporary tables and the stack of active recursive calls.