Space Complexity

/speɪs kəmˈplɛk.sɪ.ti/ · Noun · Development · Origin: 1965

Definitions

  1. A measure of the amount of memory an algorithm requires as a function of input size. Distinct from time complexity — some problems can be solved in polynomial time but require exponential space, or vice versa.

    In plain English: How much memory an algorithm needs as the input gets bigger. Sometimes you can trade memory for speed, or speed for memory.

    Example: "The recursive solution uses O(n) space on the call stack; the iterative DP version brings it down to O(1) with two variables."

Related Terms