How to Calculate the Running Time of an Algorithm | DSA Tutorials

How to Calculate Running Time of Algorithm – To calculate the running time of an algorithm, we have two types of approaches. One is an experimental method, and the other is an analytical method.

Methods to Calculate the Running Time of an Algorithm

1. Experimental method
2. Analytical method

Experimental Method

In the experimental method, we implement an algorithm in a particular language and run it on different inputs and then record the exact running time of the algorithm. But this method depends on the software and hardware that we are using to implement the algorithm. So this is a dependent method. And this approach may not be good because sometimes it will give an incorrect answer.

Let’s see how with the help of an example.

Let’s take two algorithms. and assume that one algorithm takes less time to execute and the other one takes more time than the first one. But if I execute the bad algorithm in a language that is very fast in terms of execution and run it on a computer that is very powerful.

And the side, if I execute a good algorithm on a computer that is very slow in terms of processing and also code the algorithm in a language that is slow in terms of execution.

Then a bad algorithm should execute in much less time than a good algorithm, and that is not true. So that’s why sometimes we get the wrong measurement of the running time of an algorithm using the experimental method. Another problem is that using experimental we can only run the algorithm on a limited number of inputs. So we don’t get the exact running time of an algorithm.

Also, one critical problem is that this approach is not feasible for algorithms that take a long time to execute. Some algorithms take hours or even a day to execute. So we need to wait for the result, and we don’t expect that a particular thing will continue to run on for a long time. And we also need a powerful machine to run these types of algorithms.

Another method we use for measuring the running time of an algorithm is the analytical method, or asymptotic analysis.

Analytical method

This is a theoretical method that analyses the running time of an algorithm based on the input size. In this method, we don’t calculate the exact running time of an algorithm. Therefore, we don’t need to run the algorithm on a system. So, using this approach, we can consider all the possible inputs. And this is a method that is independent of the software and hardware. So we got the possible running time for an algorithm.

Asymptotic analysis of the algorithm

Asymptotic analysis is a technique that calculates the running time of an algorithm as a function of the input size. In other words, we can say that it shows us that the running time of an algorithm increases with the input size. If the size of the input increases, the running time of the algorithm will increase. Therefore, the small input size of the algorithm has less running time, and the big input size algorithm has more running time. If the input size is doubled, then the running time might double, quadruple, or increase 100 times more.

Let’s take two algorithms A and B as shown in Figure 1. When the input size increases, the running time of both algorithms also increases. On the input size of 2, both algorithms have the same running time. But as the input size increases, algorithm B needs more time than algorithm A to run. So that’s why algorithm B is not suitable for our program. Now, let’s take an algorithm like the one shown in Figure 1.

To calculate the running time of an algorithm, first of all, we calculate how many operators and inputs are in the algorithm. So, as shown in Figure 1, the algorithm has one input and three operators. One is an assignment, one is the comparison, and the other is the arithmetic operator.

So the running time of an algorithm is the sum of the running time of all the inputs and operations performed in the algorithm. We give a unique name to each of the operations and input as shown in Figure 2. So we can write the running time of the algorithm as shown in Figure 2.

Here we multiply the comparison operation by n because it performs n times in the for-loop. So, using the rules of big O notation, we can say that this algorithm has an order of n, and take the running time approximately equal to the running time of n.

Note – To determine the efficiency of an algorithm, we need to find out how the algorithm behaves when the input size is increased. So, to find the efficiency of an algorithm, we use Big O notation.