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