CMSC 341 Asymptotic Analysis Complexity How many resources will it take to solve a problem of a given size Expressed as a function of problem size beyond some minimum size time space how do requirements grow as size grows Problem size 8 3 07 number of elements to be handled size of thing to be operated on UMBC CMSC 341 AA2 color 2 The Goal of Asymptotic Analysis How to analyze the running time aka computational complexity of an algorithm in a theoretical model Using a theoretical model allows us to ignore the effects of Which computer are we using How good is our compiler at optimization We define the running time of an algorithm with input size n as T n and examine the rate of growth of T n as n grows larger and larger and larger 8 3 07 UMBC CMSC 341 AA2 color 3 Growth Functions Constant T n c ex getting array element at known location any simple C statement e g assignment Linear T n cn possible lower order terms ex finding particular element in array of size n i e sequential search trying on all of your n shirts 8 3 07 UMBC CMSC 341 AA2 color 4 Growth Functions cont Quadratic T n cn2 possible lower order terms ex sorting all the elements in an array using bubble sort trying all your n shirts with all your n ties Polynomial T n cnk possible lower order terms ex finding the largest element of a k dimensional array looking for maximum substrings in array 8 3 07 UMBC CMSC 341 AA2 color 5 Growth Functions cont Exponential T n cn possible lower order terms ex constructing all possible orders of array elements Towers of Hanoi 2n Recursively calculating nth Fibonacci number 2n Logarithmic T n lg n possible lower order terms ex finding a particular array element binary search any algorithm that continually divides a problem in half 8 3 07 UMBC CMSC 341 AA2 color 6 A Graph of Growth Functions 8 3 07 UMBC CMSC 341 AA2 color 7 Expanded Scale 8 3 07 UMBC CMSC 341 AA2 color 8 Asymptotic Analysis How does the time or space requirement grow as the problem size grows really really large We are interested in order of magnitude growth rate We are usually not concerned with constant multipliers For instance if the running time of an algorithm is proportional to let s suppose the square of the number of input items i e T n is c n2 we won t usually be concerned with the specific value of c Lower order terms don t matter 8 3 07 UMBC CMSC 341 AA2 color 9 Analysis Cases What particular input of given size gives worst best average complexity Best Case If there is a permutation of the input data that minimizes the run time efficiency then that minimum is the best case run time efficiency Worst Case If there is a permutation of the input data that maximizes the run time efficiency then that maximum is the best case run time efficiency Average case is the run time efficiency over all possible inputs Mileage example how much gas does it take to go 20 miles Worst case all uphill Best case all downhill just coast Average case average terrain 8 3 07 UMBC CMSC 341 AA2 color 10 Cases Example Consider sequential search on an unsorted array of length n what is time complexity Best case Worst case Average case 8 3 07 UMBC CMSC 341 AA2 color 11 Definition of Big Oh T n O f n read T n is in Big Oh of f n if and only if T n cf n for some constants c n0 and n n0 This means that eventually when n n0 T n is always less than or equal to c times f n The growth rate of T n is less than or equal to that of f n Loosely speaking f n is an upper bound for T n NOTE if T n O f n there are infinitely many pairs of c s and n0 s that satisfy the relationship We only need to find one such pair for the relationship to hold 8 3 07 UMBC CMSC 341 AA2 color 12 Big Oh Example 8 3 07 Suppose we have an algorithm that reads N integers from a file and does something with each integer The algorithm takes some constant amount of time for initialization say 500 time units and some constant amount of time to process each data element say 10 time units For this algorithm we can say T N 500 10N The following graph shows T N plotted against N the problem size and 20N Note that the function N will never be larger than the function T N no matter how large N gets But there are constants c0 and n0 such that T N c0N when N n0 namely c0 20 and n0 50 Therefore we can say that T N is in O N UMBC CMSC 341 AA2 color 13 T N vs N vs 20N 8 3 07 UMBC CMSC 341 AA2 color 14 Simplifying Assumptions 1 If f n O g n and g n O h n then f n O h n 2 If f n O kg n for any k 0 then f n O g n 3 If f1 n O g1 n and f2 n O g2 n then f1 n f2 n O max g1 n g2 n 4 If f1 n O g1 n and f2 n O g2 n then f1 n f2 n O g1 n g2 n 8 3 07 UMBC CMSC 341 AA2 color 15 Example Code a b sum int y Mystery 42 Complexity 8 3 07 UMBC CMSC 341 AA2 color 16 Example Code sum 0 for i 1 i n i sum n Complexity 8 3 07 UMBC CMSC 341 AA2 color 17 Example Code sum1 0 for i 1 i n i for j 1 j n j sum1 Complexity 8 3 07 UMBC CMSC 341 AA2 color 18 Example Code sum1 0 for i 1 i m i for j 1 j n j sum1 Complexity 8 3 07 UMBC CMSC 341 AA2 color 19 Example Code sum2 0 for i 1 i n i for j 1 j i j sum2 Complexity 8 3 07 UMBC CMSC 341 AA2 color 20 Example Code sum 0 for j 1 j n j for i 1 i j i sum for k 0 k n k a k k Complexity 8 3 07 UMBC CMSC 341 AA2 color 21 Example Code sum1 0 for k 1 k n k 2 for j 1 j n j sum1 Complexity 8 3 07 UMBC CMSC 341 AA2 color 22 Example Using Horner s rule to convert a string to an integer static int convertString String key int intValue 0 Horner s rule for int i 0 i key length i intValue 37 intValue key charAt i return intValue 8 3 07 UMBC CMSC 341 AA2 color 23 Example …