CH-1.2 Performance analysis for mca.pptx

CH-1.2 Performance analysis

1. DISCOVER . LEARN . EMPOWER UNIT-1 UNIVERSITY INSTITUTE OF COMPUTING MASTER OF COMPUTER APPLICATIONS DESIGN AND ANALYSIS OF ALGORITHMS 23CAH-511 1

2. Introduction : Characteristics of Algorithms, Algorithm Specification, Analysis Framework, Performance Analysis: Space complexity, Time Complexity. DESIGN AND ANALYSIS OF ALGORITHMS CO Number Title Level CO1 Understand the basics of different data structures to manage the data Remember   CO2 CO3 Analyze the asymptotic performance of algorithms through algorithmic complexity of simple, non-recursive programs. Understand the fundamentals of data structures Understand Understand   Course Outcome 2

3. Outline Algorithm Specification Performance Analysis Asymptotic Notations Recursive and non-recursive algorithms Sorting and Searching algorithms Fundamentals of Data Structures 3

4. Performance Analysis Performance of an algorithm is a process of making evaluative judgment about algorithms. We can also defined as: Performance of an algorithm means predicting the resources which are required to an algorithm to perform its task. Performance of an algorithm depends on the following elements... Whether that algorithm is providing the exact solution for the problem? Whether it is easy to understand? 4

5. Contd … Whether it is easy to implement? How much space (memory) it requires to solve the problem? How much time it takes to solve the problem? Etc., Performance analysis of an algorithm is performed by using the following measures... Space required to complete the task of that algorithm ( Space Complexity ). It includes program space and data space Time required to complete the task of that algorithm ( Time Complexity ) 5

6. Time Complexity When we calculate time complexity of an algorithm, we consider only input data and ignore the remaining things, as they are machine dependent. We check only, how our program is behaving for the different input values to perform all the operations like Arithmetic, Logical, Return value and Assignment etc. The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution. 6

7. Space Complexity When we design an algorithm to solve a problem, it needs some computer memory to complete its execution. For any algorithm, memory is required for the following purposes... Memory required to store program instructions Memory required to store constant values Memory required to store variable values And for few other things Space complexity of an algorithm can be defined as follows... Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of that algorithm. 7

8. Frequently Asked Questions Differentiate between time complexity and space complexity. How the performance can be analyzed? Explain with the example. 8

9. References [1] https:// swordrock.files.wordpress.com /2010/09/ daie-algorithms.png [2] https:// static.javatpoint.com /tutorial/ daa /images/ daa-tutorial.png Books: Introduction to Algorithms by Coreman , Leiserson , Rivest , Stein. Fundamentals of Algorithms by Ellis Horwitz Computer Algorithms/C++ by Sartaj   Sahni , Sanguthevar Rajasekaran 9

10. THANK YOU 10