DOC PREVIEW
MIT 6 001 - Orders of Growth

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.001 Recitation 4: Orders of GrowthRI/Substitute: Gerald Dalley, [email protected] Feb 2007Announcements / Notes• No classes Monday. Tuesday is a virtual Monday.If you normally attend a Tuesday tutorial, try toattend any tutorial, but stick with your TA if atall possible.• Project 1 is due on 2 March 2007. It’s new! It’sfun! It’s cryptic!• InstaQuiz discussionApocryphaKings, wheat, chessboards, orders of growth, and18,446,744,073,709,551,615.DefinitionsTheta (Θ) notation:f(n) = Θ(g(n)) → k1·g(n) ≤ f (n) ≤ k2·g(n), for n > n0Big-O notation:f(n) = O(g(n)) → f (n) ≤ k · g(n), for n > n0Adversarial approach: For you to s how thatf(n) = Θ(g(n)), you pick k1, k2, and n0, then I (theadversary) try to pick an n which doesn’t satisfyk1· g(n) ≤ f(n) ≤ k2· g(n).Time order of growth: how many primitive opera-tions are evaluated?Space order of growth: maximum number of pendingoperations.ImplicationsIgnore constants. Ignore lower order terms. For asum, take the larger term. For a product, multiplythe two terms. Orders of growth are concerned withhow the effort scales up as the size of the problemincreases, rather than an exact measure of the cost.Typical Orders of Growth• Θ(1) - Constant growth. Simple, non-looping,non-decomposable operations have constantgrowth.• Θ(log n) - Logarithmic growth. At each itera-tion, the problem size is scaled down by a con-stant amount: (recur (/ n c)).• Θ(n) - Linear growth. At each iteration,the problem size is decremented by a constantamount: (recur (- n c)).• Θ(n log n) - Nifty growth. Nice recursive solutionto normally Θ(n2) problem.• Θ(n2) - Quadratic growth. Computing corre-spondence between a set of n things, or doingsomething of cost n to all n things both result inquadratic growth.• Θ(2n) - Exponential growth. Really bad.Searching all possibilities usually results in ex-ponential growth.(+ (recur (- n c1)) (recur (- n c2))).What’s n?Order of growth is always in terms of the size of theproblem. Without stating what the problem is, andwhat is considered primitive (what is being countedas a “unit of work” or “unit of space”), the order ofgrowth doesn’t have any meaning.1Problems1. Give order notation for the following:(a) 5n2+ n A(b)√n + n A(c) 3nn2A2. Consider the following implementation of factorial:(define (fact n)(if (= n 0)1(* n (fact (- n 1)))))Show the steps in the substitution model for (fact5). Only write out the steps which introduce a newrecursive call or are a base case.( fact 5)Running time? A Space? A3. Consider the following approximation to the constant e = 1 +11!+12!+13!+14!+ ...(define (find-e n)(if (= n 0)1.(+ (/ (fact n)) (find-e (- n 1)))))Running time? A Space? A4. Assume you have a procedure (divisible? n x) which returns #t if n is divisible by x. It runs inO(n) time and O(1) space. Write a procedure prime? which takes a number and returns #t if it’s primeand #f otherwise. You’ll want to use a helper procedure.; As sume n is p os it iv e( def ine ( prime ? n)Running time? A Space? A2InstaQuizName:1. Write a procedure that computes the number of decimal digits in it’s input. Do not use logs.(num-digits 102) → 3; As s u mes n is n o n - n e g a ti v e( def ine ( n um-dig i ts n)2. Write a procedure that will multiply two numb ers together, but the only arithmetic operation allowed isaddition (i.e. multiplication through repeated addition). In addition, your procedure should be iterative,not recursive.(slow-mul 3 4) → 12; As s u mes a , b are n o n - n e g a ti v e( def ine ( slow- mul a b)3. On Wednesday, we have a bonus recitation (since there’s no lecture on Tuesday). B y default, we’ll keepdiving into orders-of-growth questions. Is there anything else that you’d like included in


View Full Document

MIT 6 001 - Orders of Growth

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Orders of Growth
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Orders of Growth and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Orders of Growth 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?