Calculate the running time of an algorithm: 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.


Calculate the running time of an algorithm

Calculate running time of an algorithm


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 maybe 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 another side, if I execute the good algorithm on a computer which is very slow in terms of processing and also code the algorithm in a language which is slow in terms of executing.

then a bad algorithm should execute in much less time then good algorithm. and that is not true. so that's why sometimes we get wrong measuring of running time of an algorithm using experimental method.

another problem is that using experimental we can only run the algorithm on the 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 the 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 and also we don't expect that a particular thing will continue to run on for a long time of 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 algorithm

asymptotic analysis is a technique that calculates the running time of an algorithm with the increases in the input size.

in other words, I can say than it shows us that the running time of an algorithm increases with the input size. 

if the size of input increase the running time of the algorithm will be increased. therefor 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 double then running time might double, quadruple, or become 100 times more. 

let's take two algorithms A and B like 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. 

Asymptotic analysis of algorithm

but as the input size increases the algorithm B needs more time then algorithm A to run. so that's why the algorithm B is not suitable for our program.

Now let's take an algorithm like shows in the image given below.

Calculate running time of an algorithm

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 to shows 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.

so 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 algorithm like shows in the image given below.

analysis of algorithm

here we multiply 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.