Asymptotic Complexity
Asymptotic complexity (or asymptotic analysis or asymptotic complexity analysis) is the use of asymptotic notation to describe the computational complexity of an algorithm.
Computational complexity of algorithm is (generally) about how it consumes computational resources, namely time complexity and space complexity.
Time Complexity
Time complexity measures the amount of time that an algorithm needs to run as a function of its input size.
We've been measuring time complexity so far.
Space Complexity
Space complexity measures the amount of memory that an algorithm needs to run as a function of its input size. That means how much memory, in the worst case, is needed at any point in the algorithm.
Similar to time complexity, we're mostly concerned with how the space consumption grows, in asymptotic terms, as the size the input grows.
Often space complexity is taken to mean auxiliary space.
-
Auxiliary space is the extra space or the temporary space used by an algorithm during it's execution.
-
We can say Space Complexity $=$ Auxiliary Space $+$ Input space.
-
When we compare two algorithm for solving a computational problem, it is arguably more useful to compare their auxiliary space usage since the input space will be the same for a given problem.
Auxiliary space and space complexity are not the same. In this class, we will specify when to find auxiliary space, but when asked for space complexity, consider that Space Complexity $=$ Auxiliary Space $+$ Input space.
Exercise Complete the following table. Use big Oh notation to asymptotically describe time/space complexities.
| Algorithm | Time Complexity | Space Complexity | Input Space | Auxiliary Space |
|---|---|---|---|---|
| Linear search | ||||
| Binary search |
Solution
The following is based on worst-case analysis.
| Algorithm | Time Complexity | Space Complexity | Input Space | Auxiliary Space |
|---|---|---|---|---|
| Linear search | $O(n)$ | $O(n)$ | $O(n)$ | $O(1)$ |
| Binary search | $O(\lg n)$ | $O(n)$ | $O(n)$ | $O(\lg n)$ or $O(1)$ |
The auxiliary space of binary search depends on its implementation. A iterative implementation takes $O(1)$ but a recursive implementation could be $O(\lg n)$ — unless the programming language used has optimization for tail recursion (beyond the scope of this course).
Please refer to this article for "Iterative vs. Recursive Binary Search Algorithm".
Resources
- Wikipedia entry on Asymptotic computational complexity.
- Baeldung's article Understanding Space Complexity.
- StudyTonight's article Space Complexity of Algorithms.
- North Western University's EECS 311 lecture notes on Space Complexity.