STUDENT NAME: 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall 2004Recitation 4Orders of GrowthDefinitionsTheta (Θ) 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 show that f (n) = Θ(g(n)), you pick k1, k2, and n0, then I (theadversary) try to pick an n which doesn’t satisfy k1· g(n) ≤ f (n) ≤ k2· g(n).ImplicationsIgnore constants. Ignore lower order terms. For a sum, take the larger term. For a product,multiply the two terms. Orders of growth are concerned with how the effort scales up as the sizeof the problem increases, 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 iteration, the problem size is scaled down by aconstant amount: (call-again (/ n c)).• Θ(n) - Linear growth. At each iteration, the problem size is decremented by a constantamount: (call-again (- n c)).• Θ(n log n) - Nifty growth. Nice recursive solution to normally Θ(n2) problem.• Θ(n2) - Quadratic growth. Computing correspondence between a set of n things, or doingsomething of cost n to all n things both result in quadratic growth.• Θ(2n) - Exponential growth. Really bad. Searching all possibilities usually results in expo-nential growth.What’s n?Order of growth is always in terms of the size of the problem. Without stating what the problemis, and what is considered primitive (what is being counted as a “unit of work” or “unit of space”),the order of growth doesn’t have any meaning.STUDENT NAME: 2Problems1. Assume you have a procedure (divisible? n x) which returns #t if n is divisible by x. Itruns in O(n) time and O(1) space. Write a procedure prime? which takes a number andreturns #t if it’s prime and #f otherwise. You’ll want to use a helper procedure.Running time?
View Full Document
Unlocking...