Analysis of Algorithms and Time Complexity

ANALYSIS OF ALGORITHMS Data Structure and Algorithms

WHAT TO LEARN Time & Space Complexity Running Time Pseudo-Code Analysis of Algorithms Asymptotic Notation Asymptotic Analysis Mathematical facts 2 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

TIME AND SPACE COMPLEXITY Complexity of an algorithm is analyzed in two perspectives:Time and Space. Time Complexity It s a function describing the amount of time required to run an algorithm in terms of the size of the input. "Time" can mean the number of memory accesses performed, the number of comparisons between integers, the number of times some inner loop is executed, or some other natural unit related to the amount of real time the algorithm will take. Space Complexity It s a function describing the amount of memory an algorithm takes in terms of the size of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself. Again, we use natural (but fixed-length) units to measure this. 3 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

AVERAGE CASE VS. WORST CASE RUNNING TIME OF AN ALGORITHM An algorithm may run faster on certain data sets than on others. Finding the average case can be very difficult, so typically algorithms are measured by the worst-case time complexity. Also, in certain application domains (e.g., air traffic control, surgery, IP lookup) knowing the worst-case time complexity is of crucial importance. worst-case }average-case? 5 ms 4 ms 3 ms best-case 2 ms 1 ms A B C D E F G Input 4 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

MEASURING THE RUNNING TIME How should we measure the running time of an algorithm? Approach 1: Experimental Study Write a program that implements the algorithm Run the program with data sets of varying size and composition. Use a method like clock( )/time( ) to get an accurate measure of the actual running time. t (ms) 60 50 40 30 20 10 n 0 50 100 5 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

BEYOND EXPERIMENTAL STUDIES Experimental studies have several limitations: It is necessary to implement and test the algorithm in order to determine its running time. Experiments can be done only on a limited set of inputs, and may not be indicative of the running time on other inputs not included in the experiment. In order to compare two algorithms, the same hardware and software environments should be used. 6 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

BEYOND EXPERIMENTAL STUDIES We will now develop a general methodology for analyzing the running time of algorithms. In contrast to the "experimental approach", this methodology: Uses a high-level description of the algorithm instead of testing one of its implementations. Takes into account all possible inputs. Allows one to evaluate the efficiency of any algorithm in a way that is independent from the hardware and software environment. 7 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

PSEUDO-CODE Pseudo-code is a description of an algorithm that is more structured than usual prose but less formal than a programming language. Example: finding the maximum element of an array. Algorithm arrayMax(A, n): Input: An array A storing n integers. Output: The maximum element in A. currentMax A[0] for i 1 to n -1 do ifcurrentMax < A[i] thencurrentMax A[i] returncurrentMax Pseudo-code is our preferred notation for describing algorithms. 8 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

PSEUDO-CODE A mixture of natural language and high-level programming concepts that describes the main ideas behind a generic implementation of a data structure or algorithm. -Expressions: use standard mathematical symbols to describe numeric and boolean expressions -use for assignment ( = in C) -use =for the equality relationship ( == in C) -Method Declarations: -Algorithm name(param1, param2) -Programming Constructs: - decision structures: - while-loops: - repeat-loops: - for-loop: for ... do - array indexing: A[i] -Methods: - calls: - returns: if ... then ... [else ... ] while ... do repeat ... until ... object method(args) return value 9 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ANALYSIS BASICS Primitive Operations: Low-level computations independent from the programming language can be identified in pseudocode. Examples: calling a method and returning from a method arithmetic operations (e.g. addition) comparing two numbers, etc. By inspecting the pseudo-code, we can count the number of primitive operations executed by an algorithm. 10 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

EXAMPLE: Algorithm arrayMax(A, n): Input: An array A storing n integers. Output: The maximum element in A. currentMax A[0] fori 1to n -1 do if currentMax < A[i] then currentMax A[i] return currentMax 11 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC NOTATION Goal: to simplify analysis by getting rid of unneeded information (like rounding 1,000,001 1,000,000) We want to say in a formal way 3n2 n2 The Big-Oh Notation: given functions f(n) and g(n), we say that f(n) is O(g(n) ) if and only if there are positive constants c and n0 such that f(n) c g(n) for n n0 12 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC NOTATION-EXAMPLE For functions f(n) and g(n) (to the right) there are positive constants c and n0 such that: f(n) c g(n) for n n0 Example Let us consider a given function,f(n)=4.n3+10.n2+5.n+1 Considering g(n)=n3 f(n) 5.g(n) for all the values of n>2n>2 Hence, the complexity of f(n) can be represented as O(g(n)) i.e.O(n3) 13 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC NOTATION-ANOTHER EXAMPLE On the other hand n2 is not O(n) because there is no c and n0 such that: n2 cn for n n0 (As the graph to the right illustrates, no matter how large a c is chosen there is an n big enough that n2>cn ) . 14 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC NOTATION (CONT.) Note: Even though it is correct to say 7n - 3 is O(n3) , a better statement is 7n - 3 is O(n) , that is, one should make the approximation as tight as possible Simple Rule: Drop lower order terms and constant factors 7n-3 is O(n) 8n2log n + 5n2 + n is O(n2log n) 15 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC NOTATION (TERMINOLOGY) Special classes of algorithms: logarithmic: linear: O(n) quadratic: O(n2) polynomial: exponential: O(log n) O(nk), k 1 O(an), n > 1 Relatives of the Big-Oh (f(n)): Big Omega--asymptotic lower bound (f(n)): Big Theta--asymptotic tight bound 16 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ASYMPTOTIC ANALYSIS OF THE RUNNING TIME Use the Big-Oh notation to express the number of primitive operations executed as a function of the input size. For example, we say that the arrayMax algorithm runs in O(n) time. Comparing the asymptotic running time -an algorithm that runs in O(n) time is better than one that runs in O(n2) time -similarly, O(log n) is better than O(n) -hierarchy of functions: log n << n << n2 << n3 << 2n Caution! Beware of very large constant factors. An algorithm running in time 1,000,000 n is still O(n) but might be less efficient on your data set than one running in time 2n2, which is O(n2) 17 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

EXAMPLE OF ASYMPTOTIC ANALYSIS An algorithm for computing prefix averages Algorithm prefixAverages1(X): Input: An n-element array X of numbers. Output: An n -element array A of numbers such that A[i] is the average of elements X[0], ... , X[i]. Let A be an array of n numbers. fori 0 ton - 1 do a 0 for j 0 toido a a + X[j] A[i] a/(i+ 1) return array A 1 step n iterations i iterations with i=0,1,2...n-1 18 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

ANOTHER EXAMPLE A better algorithm for computing prefix averages: Algorithm prefixAverages2(X): Input: An n-element array X of numbers. Output: An n -element array A of numbers such that A[i] is the average of elements X[0], ... , X[i]. Let A be an array of n numbers. s 0 for i 0 tondo s s + X[i] A[i] s/(i+ 1) return array A 19 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms

Thank You! Next Class Array Data Structure 20 Ashish Kumar AP, Dept. of IT, MIT Muzaffarpur DSA - Analysis of Algorithms