Time complexity vs. space complexity
There are multiple ways to design an algorithm, or considering which one to implement in an application. When thinking through this, it’s crucial to consider the algorithm’s time complexity and space complexity.
Time complexity
The time complexity of an algorithm is the amount of time taken by the algorithm to complete its process as a function of its input length, n. The time complexity of an algorithm is commonly expressed using asymptotic notations:
- Big O - (n),
- Big Theta - (n)
- Big Omega - (n)
Space complexity
The space complexity of an algorithm is the amount of space (or memory) taken by the algorithm to run as a function of its input length, n. Space complexity includes both auxiliary space and space used by the input.
Auxiliary space is the temporary or extra space used by the algorithm while it is being executed. Space complexity of an algorithm is commonly expressed using Big O notation.
Many algorithms have inputs that can vary in size, e.g., an array. In such cases, the space complexity will depend on the size of the input and hence, cannot be less that for an input of size . For fixed-size inputs, the complexity will be a constant .
It’s valuable for a programmer to learn how to compare performances of different algorithms and choose the best time-space complexity to solve a particular problem in the most efficient way possible.
RELATED TAGS
