The temporal (or time) complexity of an algorithm is a measure of the time the algorithm takes to be executed and give an output, as a function of the size of the input.
The time complexity can be calculated in two ways:
- Practical
- Theoretical
Practical temporal complexity
The practical way depends on the specific implementation of the algorithm, the computer used, the programming language, how many resources the computer has available, etc.
Like in everything, there are pros and cons. The pros are that you can know with certainty how much time the algorithm needs to give the output for a specific input, and in a specific computer.
The cons are that you actually need to implement the algorithm the be able to calculate its practical time complexity. What happens for a different input? We don’t know.
To solve the previous issue, we can use the theoretical method.
Theoretical temporal complexity
The theoretical method allows us to calculate the temporal complexity of an algorithm for variable input sizes. This allows us to have a better idea of how long the algorithm will take to be executed for all the possible inputs.
The cons, in this case, are that it is difficult to calculate for large/complex algorithms, and in many cases impractical.
But, why do we need to calculate the temporal complexity anyway?
Why do we need temporal complexity?
In programming, and many other areas, there are several ways to solve the same problem.
If we have three different algorithms that solve the same problem, which one we suppose to use?
We are always supposed to use an efficient algorithm. The efficient algorithm to solve a problem is the one with lower temporal complexity.
A note here. There is another way to compare algorithms: spatial complexity. But, that way is out of the scope of this post.
So, temporal complexity is important because it tells us when an algorithm is better than another one (considering the time), assuming that both solve the same problem. A major advantage of the theoretical way of calculating the time complexity is that it is independent of programming languages, computers, etc. Also, you don’t need to implement the algorithm to calculate the theoretical temporal complexity, which helps us because we then implement the algorithm only when we are sure that is the efficient one.
It is of utmost importance that the temporal complexity of an algorithm always depends on the input size. I’ll show some examples in the next post.
Also, sometimes the temporal complexity depends on the characteristics of the input.
For this reason, when calculating the temporal complexity, we can calculate three measures:
- Best case
- Average case
- Worst case
It is usual, to only calculate the temporal complexity in the worst-case scenario.
In the next post, I’ll show you some examples of calculating the practical/real temporal complexity of some algorithms.