Measuring algorithm performance

Measuring the performance of algorithm, in terms of Big(O), theta, and Omega notation with respect to their Scientific notation like Worst, Average, Best, cases

1. Measure Algorithm Performance   By: Asfaw Alene &Habitamu Asimare Bahir Dar Institute of Technology, BiT Algorithm Analysis Submitted to: Dr Million M. 06/20/2018

2. Outline Overview Asymptotic Notations Analysis Average Best Worst-Case Concluding References

3. 1. Overview of Algorithm An algorithm is a step by step procedure for solving a problem, based on conducting a sequence of specified actions. A computer  program  can be viewed as an elaborate algorithm. In mathematics and computer science, an algorithm usually means a finite procedure that solves a real world problem . An algorithm can be used in For search engines Encryption technique Memory management Resource allocation (Operating Systems implementations)

4. Continued… Basically Algorithm plays a great role to make computers system efficiently. The following is the points to be remembered in Algorithm An algorithm is a sequence of unambiguous instructions. An algorithm  is a well-defined procedure that allows a computer to solve a problem The algorithm is described as a series of logical steps in a language that is easily understood Algorithms is computer understandable actions that can be implemented in Programming languages In fact, it is difficult to think of a task performed by your computer that does not use algorithms.

5. 2. Asymptotic Notations Three asymptotic notations are mostly used to represent time complexity of algorithms. The theta( Θ ) Notation bounds a functions from above and below, so it defines exact asymptotic behavior. A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants. For example, consider the following expression. 3n 3  + 6n 2  + 6000 = Θ(n 3 ) Big O Notation defines an upper bound of an algorithm, it bounds a function only from above. have to use two statements for best and worst cases in theta notations: 1. The worst case time complexity of Insertion Sort is Θ(n^2). 2. The best case time complexity of Insertion Sort is Θ(n). In case of Big O notations we select worst case which is O(n^2) Omega( Ω ) Notation Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound the Omega notation is the least used notation among all three.

6. 3. Analysis We can have three cases to analyze an algorithm: Worst Case In the worst case analysis, we calculate upper bound on running time of an algorithm.  We must know the case that causes maximum number of operations to be executed. Average Case n average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. Best Case we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed.

7. Asymptotic notations with examples 1 < logn < < n < nlogn< n < n 2 <n 3 < ……. 2 n < 3 n < .. n n   Lower bound Upper bound Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis. The mostly used asymptotic notations Big O Notation: Θ Notation Ω Notation

8. Big O-Notation (Upper limit ) For the function F(n) = O(n) , iff there exists positive constants c and n0 , such that f(n) ≤ c* g(n) for all n ≥ n0. Example f(n)= 2n+3; what is the time complexity of F(n) ? Solution chose the c value and g(n) value on the since O notation is the upper bound so it is only possible to chose the upper value. so we can chose c=10, and g(n)=n , for n>=1 2n+3 <10n is true the time complexity of F(n) will be = O(n).

9. Omega Ω Notation (lower bound ) For the function F(n) = Ω ( n) , iff there exists positive constants C and n0 , such that f(n) ≥ c* g(n) for all n ≥ n0. Example f(n)= 2n+3; what is the time complexity of F(n) ? Solution chose the c value and g(n) value on the since Ω notation is the upper bound so it is only possible to chose the upper value. so we can chose c=1, and g(n)=n , for n>=1 2n+3 > n is true the time complexity of F(n) will be = Ω (n).

10. Omega Ω Notation (lower bound ) For the function F(n) = Ω ( n) , iff there exists positive constants C and n0 , such that f(n) ≥ c* g(n) for all n ≥ n0. Example f(n)= 2n+3; what is the time complexity of F(n) ? Solution chose the c value and g(n) value on the since Ω notation is the upper bound so it is only possible to chose the upper value. so we can chose c=1, and g(n)=logn , for n>=1 2n+3 > logn is true the time complexity of F(n) will be = Ω ( logn ).

11. Theta Θ-Notation (contd) For the function F(n) = Θ(g(n)) , iff there exists positive constants c1, c2 and n0 , such that c1* gn <= f(n) ≤ c2* g(n) for all n ≥ n0. } Example f(n)= 2n+3; what is the time complexity of F(n) ? Solution chose the c1,c2 value and g(n) value on the since Θ notation is the average bound so it is only possible to chose the value which is the multiple of n. so we can chose c1=1, c2 = 5, and g(n)=n , for n>=1 1n< 2n+1<5n is true, so the time complexity of F(n) will be = Θ(n).

12. Best Case Analysis (contd …) Consider for the following example A linear searching From this example if we are searching a key element that are present at first index is called best case Best case time will be = 1, i.e B(n) or we can use notations Big-O Notation and will be O(n)=1; 2 8 6 12 5 7 9 4 3 16

13. Worst Case Analysis In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed.  Consider for the following example A linear searching worst case analysis From this example if we are searching a key element that are present at last of the index elements are called best case 2 8 6 12 5 7 9 4 3 16

14. Average Case Analysis Consider for the following example A linear searching average case analysis From this example if we are searching a key element that are present at middle of the index elements are called best case. If we are looking from n elements will be A(n)= (n+1)/2 What if you are given to analyze the case’s in Binary Search Tree ? 8 6 12 5 7 9 4 3 16

15. Advantage and disadvantages Advantages Disadvantages To understand the complexity that the program require does not account for memory access times to minimize unnecessary operations data size can determines the algorithm behavior solve real-world problem sometimes the best and worst cases boundary can’t algorithm performance

16. 4. Conclusion Algorithms are the backbone of the working structure of computer system. Effectiveness and Correctness allows us to analyze the performance of algorithm. Beyond working on algorithm we have two think of two major aspects of algorithm Time : Instructions take time. How fast does the algorithm perform? What affects its runtime? Space : Data structures take space What kind of data structures can be used? How does choice of data structure affect the runtime? So space and time is challenges of algorithm performance

17. Continued… Strength of measuring algorithm performance analysis It expresses the amount of work for a given algorithm as being proportional to a bounding function. Weakness of measuring algorithm performance analysis independent of implementation details such as the choice of computer hardware The asymptotic notation can be equal in some cases, like worst and best cases. SO that when the performance of algorithm is done, the analysis should include what type of the resource should support while implementing/coding the algorithm

18. 5. Reference Weiss, M.A., Data Structures and Problem Solving Using JAVA, Third Edition, AddisonWesley Publishing Company, Inc., Reading, MA, 2006, pp. 313-331. Cormen , T. H., Leiserson , C. E., Rivest , R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed ). MIT Press Musselman , R. (2007). Robustness: A better measure of algorithm performance. Thesis, Naval Postgraduate School, Monterey, CA. McMaster, K., Sambasivam , S., Rague , B., & Wolthuis , S. (2015). Distribution of Execution Times for Sorting Algorithms Implemented in Java. Proceedings of Informing Science & IT Education Conference ( InSITE ) 2015, 269- 283 Mr. Rajinikanth B., What is Performance Analysis of an algorithm? , 2009, http://btechsmartclass.com/DS/U1_T2.html last accessed on 17 June 2018.

19. Thank You!