New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mr. Hayley Barton


Mr. Hayley Barton

GPA 3.93


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




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.




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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.