Unit – 1 Basics of analysis of an Algorithm.pptx

basis of analysis of an algorithm

1. Analysis of Algorithm

2. Algorithm An Algorithm is a sequence of steps to solve a problem. In other words, an Algorithm is defined as a collection of unambiguous instructions occurring in some specific sequence and produces output for a given set of inputs some finite amount of time.

3. From Coremen “An algorithm is well-defined computational procedure that takes some value, or set of values as input and produces some value, or set of values as output. “ Thus an algorithm is a sequence of computational steps that transform the input into the output.

4. Properties of Algorithm 1. Non-ambiguity 2. Range of Input 3. Multiplicity 4. Speed 5. Finiteness

5. Non-ambiguity Each step in algorithm should be non-ambiguous. Each instruction should be clear and precise. Any instruction should not have any conflicting meaning. This property also indicates "effectiveness" of algorithm. Range of Input The range of input should be specified. Normally algorithm is input driven and if range of input is not specified, then algorithm may go in infinite state. Finiteness The algorithm should be finite. i.e. after performing required operations it should be terminated. Multiplicity The same algorithm can be represented in several different ways. i.e. for solving same problem we may be able to write several different algorithms. For example, to search number from the given list we can either use "SEQUENTIAL SEARCH" method or "BINARY SEARCH" method. Speed The algorithm are written using some specific ideas (popularly known as logic). The logic of the algorithm should be written in such a way that it can produce output with fast speed, thus, it should be "efficient".

6. Analysis of an Algorithm Analysis of an algorithm means to find out the resources required by an algorithm. Resources of an algorithm may be: Time Space Power consumption Communication Bandwidth Computer Hardware, etc. It usually involves determining a function that relates the length of algorithm input to no. of steps it takes (TIME COMPLEXITY) or no. of storage (SPACE COMPLEXITY) locations it uses.

7. Complexity Time Complexity Time complexity of an algorithm signifies the total time required by the program to run till its completion. Space Complexity Space complexity of an algorithm signifies the total amount of memory or storage an algorithm needs.

8. Best Case Complexity " If an algorithm takes minimum time to solve the problem for a given set of input, it is called best case time complexity. “ For example, Suppose we want to search an element from the list, and the element is found at first location, then only one comparison is required (linear search). So, it is called best case time complexity. So, best case time complexity of linear search is O(1).

9. Average Case Complexity "In an algorithm takes average amount of time to solve the problem for given set of input, then it is called average case time complexity.“ Average case occurs with some random sequence of input data. Average case analysis gives general behavior of an algorithm. For example, In linear search average case occurs when required element is neither at first location nor at last location but it is somewhere at in between position. Average case time complexity of linear search is O(n+1)/2 or O(n)/2 that means algorithm scans about half of the elements from the list.

10. Worst Case Complexity "If an algorithm takes maximum time to solve the problem for given set of input, it is called worst case time complexity. “ For example, Suppose we want to search an element from the list, and the element is found at the last location (or not found at all) then we have to perform n comparison, where n is the size of the list. So, it is called worst case time complexity. Worst Case Time Complexity of linear search is O(n).

11. Thank You