Understanding complexity of algorithm
Complexity of an algorithm can be measured by the time and space it takes to run and produce desired output. The less time and space an algorithm requires, the more efficient that algorithm is.
There are two ways as we know to calculate the compexity of an algorithm:
- Time complexity
- Space complexity
Analysis of an algorithm is very important. For solving a problem there might exist multiple solutions, but we have to choose the one that is most efficient in term of time as well as space. Time and space complexity helps you find a optimised solution for given problem.
Let’s understand time and space complexity in simpler way:
Time Complexity
Time complexity is basically the time that an algorithm takes to run.
It is the iterations that it perform to produce a desired output.
Time complexities can be measured from best to worst (top to bottom)
- O(1) -> Constant time
- O (log n) -> Logarithmic
- O(n) -> Linear time
- O(n log n) -> Linearthmic
- O(n**2) -> Quadric
- O(n**3) -> Cubic
- O(2 ** n) -> Exponential
- O(n!) -> Factorial
Constant time is the best case when the algorithm doesn't depends upon the input size.
Finding all permutations of a string take n! time.
Sorting using merge sort takes O( n log n) time
Iterating through n x m matrix takes O(n*m) times.
These are few examples.
Time complexity can also be affected by the operating system as well as the hardware.
Let’s see time complexity for most commonly used algorithms.
Linear search has time complexity of O(n)
Binary search has O(log n)
Quick sort has O(n log n)
Selection sort has O(n * n)
Travelling salesperson algorithm has time complexity of O(n!)
Space Complexity
Space complexity of an algorithm is generally the space used by the algorithm based on its input. It consist of auxiliary space as well as space used by input.
Auxiliary space is the extra or temporary space used by the algorithm.
Let’s suppose we have an array to the length of n then the space complexity is O(n).
if we have a matrix of m*n then we have space complexity of O(m*n).
I hope you have clear understanding of how the space and time complexity works and how we can choose which one are the best for us.
Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we have covered few of the most commonly used algorithms using javascript.
