Sometimes there are multiple ways to solve a problem, and we need to compare these different algorithms to find which one is the best.
We can compare algorithms by two factors – Time and space.
1. Time complexity or The RAM model of computation
Time complexity is about how the time it takes increases as the number of data increases, and space complexity is the amount of space or memory taken by an algorithm to run as the number of data increase.
We can not compare algorithms by calculating the amount of time taken would not work, as different algorithms will perform differently on different configuration and diverse hardware/ environment and so very different time for running the algorithm.
So we think about the running time of the algorithm as a function of the size of its input. To calculate the time complexity of an algorithm, we measure the run time of an algorithm by summing up the number of steps needed to execute the algorithm on a set of data. This process of measuring the efficiency of algorithms in terms of mathematical functions is called Asymptotic notation.
There are specific rules set to calculate this:
- Basic logical or arithmetic operations (+, *, =, if, call) are considered to be simple operations that take a one-time step.
- Loops and subroutines are complex operations composed of multiple time steps.
- All memory access takes a precisely one-time step.
As we understand that time complexity is running time as a function of input size, to compare the algorithms, we can see how fast their functions grow.
There are three bounding functions to consider when talking about the complexity of an algorithm, the upper bound, the lower bound, and a tight bound:
- Upper bound: f(n) = O(g(n)) – means f grows no faster than g(n)
- Lower bound: f(n) = ?(g(n)) – means f grows no slower than g(n)
- Tight bound: f(n) = ?(g(n)) – means f grows exactly like g(n)
If you want to understand these bounds in detail, you can read more on this question on StackOverflow or can read these on Khan academy.
2. Space Complexity
The space complexity is the amount of working storage or memory taken by an algorithm to run in terms of the function of input size.
Space Complexity(s(P)) of an algorithm is total space taken by the algorithm to complete its execution with respect to the input size. It includes both Constant space and Auxiliary space.
S(P) = Constant space + Auxiliary space
Space complexity is sometimes ignored because the space used is minimal and/or obvious, but sometimes it becomes as important an issue as time.