**: 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 the 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 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 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 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 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 double 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.

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

Also, read other tutorials as well

- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Priority queue
- Polish notation
- Tree in the data structure
- Binary tree
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures

## 0 Comments