Space complexity is the amount of memory required to solve a computational problem, including input and auxiliary space. It is usually expressed asymptotically in big O notation, such as O(n), O(nlog n), O(nα), O(2n), etc., where n is a characteristic of the input.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more conceptsCarnegie Mellon University
Spring 2023
This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.
No concepts data
+ 29 more concepts