The best algorithm to solve a particular problem at hand is no doubt the one that requires less memory space and takes less time to complete its execution. But practically, designing such an ideal algorithm is not a trivial task. There can be more than one algorithm to solve a particular problem. One may require less memory space, while the other may require less CPU time to execute. Thus, it is not uncommon to sacrifice one thing for the other. Hence, there exists a time–space trade-off among algorithms
So, if space is a big constraint, then one might choose a program that takes less space at the cost of more CPU time. On the contrary, if time is a major constraint, then one might choose a program that takes minimum time to execute at the cost of more space
Expressing Time and Space Complexity
The time and space complexity can be expressed using a function f(n) where n is the input size for a given instance of the problem being solved. Expressing the complexity is required when
- We want to predict the rate of growth of complexity as the input size of the problem increases
- There are multiple algorithms that find a solution to a given problem and we need to find the algorithm that is most efficient.
The most widely used notation to express this function f(n) is the Big O notation. It provides the upper bound for the complexity