Complexity Analysis of an Algorithm

The efficiency of an algorithm is measured based on space usage and time consumption. We will say that this algorithm is efficient if it consumes less space and takes less time to execute. Though in reality both can not be achieved simultaneously. In this tutorial, we will discuss different techniques of complexity analysis along with methods of efficiency measurement.

---

The efficiency of an Algorithm

---

A problem may have many algorithmic solutions. Among them, one is chosen that works efficiently in terms of different metrics used for comparing the performance of the algorithms.

The complexity of an algorithm is represented by a function, which describes efficiency in terms of time or memory consumption. These complexity measurements are known as time complexity and space complexity, which are discussed below.

---

Time complexity

---

Time complexity does not represent the actual time (real clock time) consumption of the algorithm with respect to the input data. But it gives a clear understanding of the performance of the algorithm in terms of time consumption with respect to the size of the input. 

Basically, the time complexity is measured in terms of the number of comparisons of data, and the number of memory access performed, which affects the actual run time of the algorithm.

---

Space Complexity

---

Space complexity represents how much additional memory/space is required by the algorithm in terms of the input size. 

It does not speak about the memory needed for storing the input data. Though it can be represented by natural units, like bytes. But the number of elements is used for this representation, instead of actual memory consumption.

In most cases, developers do not consider space complexity. But remember that the importance of space complexity is not less than time complexity. And sometimes, it becomes so important that developers may need to compromise with time complexity.

For both time and space, designers are interested in asymptotic complexity, to analyze the performance of the algorithm where the input size is very large.

Happy Exploring!