DATA STRS PROG METH
DATA STRS PROG METH COMPSCI 061BL
Popular in Course
Popular in ComputerScienence
This 6 page Class Notes was uploaded by Mr. Hayley Barton on Thursday October 22, 2015. The Class Notes belongs to COMPSCI 061BL at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/226663/compsci-061bl-university-of-california-berkeley in ComputerScienence at University of California - Berkeley.
Reviews for DATA STRS PROG METH
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/22/15
0361B Fall 2002 Discussion 6 Amir Kamil UC Berkeley 10302 Topics Order of Growth 1 Order of Growth 11 Motivation 0 Since there are often many possible algorithms or programs that compute the same results we would like to use the one that is fastest o How do we decide how fast an algorithm is Since knowing how fast an algorithm runs for a certain input does not reveal anything about how fast it runs on other inputs we need another measure that tells us how fast it is for any input A formula that relates input size to the running time of the algorithm satis es this requirement 0 We also want to ignore machine dependent factors If an algorithm takes two seconds on one machine for a given input a trivial way to get it to run in one second is to use a machine that is twice as fast There is a constant multiplicative factor relating the speed of an algorithm on one machine and its speed on another which we will ignore 0 We are only interested in how fast an algorithm runs on large inputs since even slow algorithms nish quickly on small inputs 12 Asymptotic Analysis Rather than specifying the exact relation between an algorithmls input and its running time we only specify how the running time scales as the input grows For example if the running time for an algorithm with input n is 4n2 we say that it s running time scales as n i 0 Also rather than giving the exact relation we are usually interested in limits on how fast or slow an algorithm is So we de ne the following notation H i We say that is bounded above by 9n if for all n gt M and for some K gt 0 K 2 in words 9n is an upper bound for if some positive multiple of is always greater than or equal to after some arbitrary number Ml Notice that this de nition ignores both constant multiplicative factors and behavior for small inputs to i Similarly we say that is bounded below by 9n if for all n gt M and for some K gt 0 K S in words 9n is a lower bound for if some positive multiple of is always less than or equal to after some arbitrary number Mi 9 We de ne a set of functions 09 such that 9n provides a lower bound for all functions in 09 in other words 6 09 if 9n is a lower bound for F We de ne a set of functions 99 such that 9n provides an lower bound for all functions in in other words 6 99 if 9n is a lower bound for i We de ne a set of functions 99 such that 9n provides both an upper bound and a lower bound for all functions in 99l in other words 6 99 if 9n is both an upper bound and a lower bound for U1 0 Now we can specify the speed of an algorithm by giving functions 9n and hn such that its running time is in 09 and in lf9n hn then its running time is in 99i n Figure 1 Functions m and W such that m e 0g 0 Sometimes We only care about an upper bound on the running time of an algorithm so We only give 9M Using it to give running mes of an algorit familiarize ourselves with the notation let s do some examples on arbitrary functions l Let wt Sn 2V Let W a Then m e g since 4gn 2 m for all a gt 1 and 2gn g m for all a gt 139 239 Let mi n2 and gn lUUUn Then mi 6 0g since ga g wt for all n gt 100039 Note that mi g 0g since you can t nd K and M such that K gm 2 f a for all a gt M try it 339 ln the gure 1 gm 6 am and m 6 am 439 Let mi lom and 57001051 ls mi in Og7 Recall the identity 0 Note that the above notation Works for arbitrary functions m and m i sp of its usage To 7 55417 loggb 7 WM Thus n 0 9W 0 long and NO 6 99 539 Let mi 101 and ga n2 ls wt in Og7 sometimes it helps to take the logarithms of both functions to decide which one is bigger 101 n2 1gllen 7 lga2 n1g1V01721gn Since 0139quot CE1 09 539 Let m 3 and gn 2 ls m in Og7 We can try taking logarithms again 3 2 1387 7 130 a lg3 7 a l 2 We might think that since 01 a 6 002 a mi 6 0g However be careful When in doubt check the de nition Can you nd K and M such that K 2 2 3 for all a gt M You will nd that you can t so in actuality mi g 0g an in Will H H u 39l i j it 0000 W W H HHHH H Hl WM 1 iMi I i u i i u soon mu man was man 1 2mm i H i 1 mm D t u i 7 a i i r 1 man 2mm 3000 own son Figure 2 Graph of n 71251112 n 0001 7 ls there a function n gt 0 such that n g 0a and n g 0a The function in gure 2 n a sin2 n 0001 satis es the above criteria 13 Algorithm Analysis 131 Iterative Algorithms running time of iterative algorithms is straightforward to compute Let f n be the time it takes one iteration of the a1gorithrn to run and 1et f2n he the number of iterations Then the running tirne of the algorithm is 0 f1 f2 Examples 1 mt 1ncrementlt1nt n i This function has one subexpression that takes constant time to execute and executes only once So it runs in 01 239 mt factor1a1lt1nt n it n1gt01 1 return n This function has a subexpression n r 1 that takes constant tirne to execute and this subexpression is executed a times so ma 1 f2n a and the function runs in 0a tirne 339 mt foolt1nt n 1n 1 forlt1rit 1 O 1 lt r1 1 1 forlt1rit 1 1 1 lt n21 return x In this case there are two loops The rst runs in On and the second in 0n so the total running time is in O n i 4 int barint n int x for int i O i lt n i for int j i j lt n j x 1 return x This function has one subexpression the inner loop that executes n times What is the running time of the 39 7 The 39 ha one A 39 of its own that executes nii times and is constant So the running time of the inner loop is in On 7 Now the problem with determining the running time of the function is that i variesi But we can make estimates as long as the estimates are greater than the actual value so let s assume that the running time of the inner loop is n Now the inner loop executes n times so the total running time is in O n2 i 5 int bazint k int n int res 0 for int i O i lt k i res k i k for int i O i lt n i res n i i return res This functions has two loops the rst of which is in 0k and the second of which is in We don7t know which of the two loops is faster since it depends on the relative sizes of k and n so we can only say that the function runs in 0k It is also possible to say that the function runs in Omazkn since we can give an upper bound on the faster loop by assuming it runs in the same amount of time as the slower loopi Note that in general it is not possible to give the running time of a multiple input function in terms of only one of its inputs 6 int foobarint k int n int res 0 for int i O i lt k i for int j 0 j lt n j res k i j return res The inner loop runs in On time and the outer loop iterates k times so the running time of this function is in 0k n i 2 1 Figure 3 Tree of recursive cans for rectorra1lt4gt 132 Recursive Algorithms Recursive a1gorithrns are somewhat harder to analyze than iterative algorithrns They usually require in ductive analysis We start at the base case and Work our wa u 39gher inputs until we see a pattern One way that helps is to draw a tree of the recursive cans with each call as a node and an edge between the caller and the callee We then count how many nodes are in the tree as a function of the input Then the running time of the algorithm is the number of nodes in the tree times the amount of time each call takes not inc1uding the recursive calls each each call rnakes Examples 1 1Dt fact0r1a121nt n i f n O i return 1 l else return n factor1a12n e 1 e draw a tree of the recursive calls in gure 339 About n recursive calls are made and each call takes constant time so the running time of factorlal 0 is in 0a 2t 1Dt fibonaccihnt n i 1f n o H n 1l return f1bonacc1ltn 7 1 f1bonacc1ltn 7 2 Again we draw a tree of the recursive cans in gure 4 The tree is a neariy complete binary tree so it has about 27 nodes in it so the running time ofthis function is in 02 Figure 4 Tree of recursive calls for nbonacms
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'