Space Complexity Analysis

A Space Complexity Analysis is an algorithm complexity analysis that focuses on Size of Data Structures used by an Algorithm to solve a Task.

• AKA: DSPACE.
• Example(s):
  • Linear Space Complexity.
  • Polynomial Space Complexity.
  • …
• Counter-Example(s):
  • Time Complexity Analysis.
• See: Space Complexity Performance Metric, Performance Metric, Computational Resource, Memory Space, Deterministic Turing Machine, Computational Problem, Algorithm, Computer Storage.

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/DSPACE Retrieved:2014-10-29.
  • In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm. It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory needed to run a given program.

2009

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Space_complexity
  • To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or complexity of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

---