Asymptotic Complexity
Asymptotic complexity (or asymptotic analysis or asymptotic complexity analysis) uses asymptotic notation to describe the computational complexity of an algorithm.
The computational complexity of an algorithm is (generally) about how it consumes computational resources, namely time complexity and space complexity.
Time Complexity
Time complexity measures the amount of time an algorithm needs to run as a function of its input size.
We've measured 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 is required in the worst case at any point in the algorithm.
Similar to time complexity, we're concerned with how the space consumption grows, in asymptotic terms, as the size of the input increases.
Often space complexity is taken to mean auxiliary space.
-
Auxiliary space is the extra space or the temporary space used by an algorithm during its execution.
-
We can say Space Complexity $=$ Auxiliary Space $+$ Input space.
-
When we compare two algorithms 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 the 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. An 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.