How to calculate Running Time of an algorithm

                                           Calculate Running Time of an Algorithm

The running time of algorithm defines the time required to execute an algorithm on the given set of inputs(n). There are mainly three types of complexity cases defines to measure the running time of an algorithm also known as Asymptotic analysis.

1) Best Case : Best case also called (Ω) omega notation which measure the best case scenario of how long an algorithm can possible take to complete given operation on (n) inputs. It's also known as lower bound.

2) Average Case: It represents by (Θ) theta notation which measure the average time requires to complete a given operation on set of inputs. It measures between upper and lower bound running time and calculate average running time.

3) Worst Case: It defines the worst case running time of an algorithm. Also represent using (Ο) Big-oh. It is the upper bound of an algorithm running time and measures the worst case scenario of how long an algorithm can possible take to complete given operation on set of inputs(n). Generally calculates worst case of an algorithm for a problem and then average and best case.

Example:- How to calculate running time of an algorithm.

Given the sequence of the Fibonacci numbers 0,1,1,2,3,5,8,13,21,..

Program for output nth Fibonacci number on given n, and analysis of running time on each step.

               Time taken per Instruction        Number of repetition       Total time taken by instruction

1. fun fib(n){            

2. if( n < 2)  return n |   constant c1     |                  1                            |                  c1

3. else{

4. t1 := 0              |        constant c2       |                 1                            |                  c2

5. t2:= 1               |         constant c3      |                  1                           |                   c3

6. while(n > 1){   |        constant c4      |                  n                            |                   c4 *n

7. sum := t1 + t2  |        constant c5      |                  n-1                         |                   c5 *(n-1)

8. t1 := t2             |        constant c6      |                   n-1                         |                   c6 *(n-1)

9. t2 := sum         |        constant c7       |                  n-1                         |                   c7 *(n-1)   

10. n := n-1         |        constant c8       |                  n-1                         |                    c8 *(n-1)

}

}

11. return sum   |       constant c9       |                 1                            |                       c9

}

Hence the above calculating instructions time and number of repetitions. Further calculate the complete running time of the algorithm as:-

for T(n)  when n>=2 (we uses) Hence T(n) =

	c2 + c3 + c4*n + c5*(n-1) + c6*(n-1) + c7*(n-1) + c8*(n-1) + c9
	= [ c2 + c3 + c9 - c5 - c6 - c7 - c8 ] + [ c4 + c5 + c6 + c7 + c8 ] * n
	= k0 + (k1*n), where k0 and k1 are constants. The running time of given algorithm is calculated step-wise. Hence overall time complexity of calculation nth Fibonacci number from given n inputs is O(n). So running time of an algorithm is important to know about the algorithm execution time which further improves and optimized according to required problems. The space and time complexity of an algorithm is important aspects which helps to measure performance and computation cost of algorithm on particular problem which will further be optimized according to requirements and resource capacity.