6.001 Tutorial 2Structure and Interpretation of Computer Programs February 21, 2006Recursion and Orders of GrowthRecursion!Components:• “Wishful thinking”/recursive case/inductive step – Reduce the problem to a “smaller” versionof the problem.• Base case – Hard code in the answer to some small(est) version of the problem.Everybody’s favorite recursive procedure( d e f i n e f a c t(lambda ( x )( i f (= x 0) ; Base ca se1 ; Base ca se answer( ∗ x ( f a c t (− x 1 ) ) ) ) ) ) ; R e c u r s i v e ca s eIteration (aka, tail recursion)The process is still defined in terms of itself, but there are no “deferred operations”. That is,nothing has to be done with the result of the smaller problem. This means Scheme doesn’t haveto remember these deferred operations.Orders of GrowthFormally,f(n) = Θ(g(n)) ⇔ k1g(n) ≤ f (n) ≤ k2g(n) for some k1, k2and n > n0f(n) = O(g(n)) ⇔ f(n) ≤ k2g(n) for some k2and n > n0f(n) = Ω(g(n)) ⇔ k1g(n) ≤ f (n) for some k1and n > n0f(n) = Θ(g(n)) ⇔ f(n) = O(g(n)) and f(n) = Ω(g(n))O is an upper-bound (which is usu ally what we care about). Ω is a lower-bound. Θ is both.n is the “size of the problem”. Make sure you’re clear on what n you’re using.IntuitionConstant factors don’t matter. O(3n) → O(n)Lower order terms go away. O(n2+ n) → O(n2)Nested processes multiply. Subsequent processes add.16.001 SICP Recursion and Orders of Growth• O(1) - C on s tant growth. Doesn’t matter how big the inpu t is. Primitive operations aregenerally assumed to be constant.• O(log n) - Logarithmic growth. At each step, the problem size is reduced by some f actor.• O(n) - Lin ear growth. At each step, the problem size is decremented by some constant.• O(n log n) - Nifty growth. Typical of algorithms that split input in half, recurse on bothhalves, and then combine the results in linear time (which are surprisingly common).• O(n2) - Quadratic growth. Linear number of linear growth processes.• O(2n) - Exponential growth. Bad. Typical of combinatorial algorithms.Orders of Growth in RealityHere’s an example of different implementations of Fibonacci with different orders of growth:Order1n=20 n=30 n=31 .. n=10000 n=100000 n=200000 n=1000000slow O(φn) 0.08 10.29 16.57iter O(n) 0.00 0.00 0.00 0.11 3.94 14.49fast O(log n) 0.01 0.58 2.29reallyfast O(log n) 0.01 0.51 2.02superfast O(log n) 0.01 0.43 1.72(digits) 4 6 7 2090 20899 41798 2089881This is approximate. There are some second-order effects that I didn’t account for. Namely, thenumbers eventually grow large enough that arithmetic takes non-constant time. This is particularlyvisible with the iter algorithm, which should take twice as long for n = 200000 as for n = 100000,but behaves like O(n2) for large n.Recursion ExercisesWhat do the following procedures mean?( d e f i n e mystery− func− 1(lambda ( x )(cond [(= x 0) #t ][(= x 1) #f ][ e l s e ( mystery− func− 1 (− x 2 ) ) ] ) ) )( d e f i n e mystery− func− 2(lambda ( x )( i f (= x 0)#f( not ( mystery− func− 2 (− x 1 ) ) ) ) ) )Write a recursive find−e that finds the nthorder approximation to e using the formula1/0! +1/1! +1/2! + · · · +1/n!.26.001 SICP Recursion and Orders of GrowthIteration exercisesIs mystery−func−1 recursive or iterative? What about mystery−func−2? Why?Ordering Orders of GrowthPut the following orders of growth into their simplest form1. O(6)2. O(n2+ 6)3. Θ(log n + 6n3+ 3n2+ 7n + 6)4. O(23n+7)5. O(log3n)6. O(log2n3)7. O(8n+ 4n)8. Ω(1000000000)9. Θ(2n+ n1000000000)j O(log(n!))Assuming that the above orders of growth are all big-O, put them in order from asymptoticallyfastest to slowest. (j Some are the same asymptotically, put these in order, too.)Can an algorithm take more space than time?Asymptotic AnalysisWhat is the time order of growth of addition? (Let n be the number of digits in the input numbers)What about multiplication?What about linear s earch?Binary search?What is the time order of growth of find−e? Space?Brainteaser1Can every recursive process be written iteratively?Brainteaser2Devise and write a numerically stable O(log n) time fib (like the “fast” Fibonacci algorithms givenin the above table).Brainteaser3Orders of growth can be used to measure useful values other than time and space. Distributed hashtables (DHT’s) are a fairly recent hot topic in peer-to-peer networks research. Each computer ina DHT has an address and connects to some subset of the other computers in the DHT in someparticular way so that it can send a message any other computer by its address very quickly. Thehop count is the number of computers a message must pass through to be delivered. The state isthe number of other computers that a computer must be connected to.36.001 SICP Recursion and Orders of GrowthA simple example of this is fully connected routing, in which every computer connects to every othercomputer. Suppose there are n computers in the DHT. A message takes O(1) hops to deliver, buteach computer must retain O(n) state.A better design is torus routing. Each computer’s address is a unique point on a toroidal grid (youcan think of this is a r egular, flat, rectangular grid, b ut the top wraps around to the bottom andthe side wraps around to the other side). Routing is then performed essentially the same way youwould navigate city blocks (assume th at the grid doesn’t have any holes). Wh at is the order of thehop count in this design? What about the order of the state?Can you devise a design in which messages take O(logn) hops to deliver and each computer mustbe connected to O(1) other
View Full Document
Unlocking...