To calculate the running time of an algorithm we have two types of approaches. One is an experimental method and the other one is an 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 an 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 be not good. because sometime 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 has 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 executing.
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 measuring 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. there are algorithms that take hours or even a day to execute. so we need to wait for the result also we don’t expect that a particular thing will continue to run on for a long time period. 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. and we analyze 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. so, 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 with increases in the input size. in other words, I 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 be increased. Therefore 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 running time might double, quadruple, or become 100 times more.
Let’s take two algorithms A and B as shown in the image given below. 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 shown in the image given below.
To calculate the running time of an algorithm, First of all, we calculate how many operators and inputs are there in the algorithm. so as shown in the image, the algorithm has one input and three operators. One is an assignment, one is the comparison and the other one 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 the image given above. so we can write the running time of the algorithm as shown in the image given below.
here we multiply the comparison operation with 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.
