6.001/Recitation 4

Rob Speer

Contents 1 Leftover problems with Church numerals 2 Orders of growth 2.1 What's n? 3 Questions 3.1 The many faces of Fibonacci

Leftover problems with Church numerals

Hard: Write (church-dec m n), which decrements a Church numeral by 1. (Are there negative Church numerals? What happens if you decrement x0?)

Write (church-sub m n), which returns m - n as a Church numeral, if m >= n.

Write (church> m n), which returns my-true or my-false depending on whether m > n.

Write (church= m n), which returns my-true or my-false depending on whether m = n.

Orders of growth

Measure how an algorithm scales (in time and space) as the input gets bigger.

O is an upper bound. Ω is a lower bound. Θ is both. We'll usually use O.

• Θ(1) is constant runtime. The size of the input doesn't matter. Primitive procedures are assumed to run in O(1).
• Θ(log n) is logarithmic runtime. If you can cut the problem size in half (or some other factor) at each step, the problem can be solved in Θ(log n).
• Θ(n) is linear growth. Each step reduces the work left to do by a constant amount.
• Θ(n log n) often means that you've found a nice efficient solution to a problem that would normally be Θ(n²).
• Θ(n²) is quadratic growth. If you have to do something of cost n to all n things, it probably grows quadratically.
• Θ(2ⁿ) is an example of exponential growth, which is bad. You get exponential growth if the problem size doubles at each recursive step.

What's n?

Orders of growth always need to be defined in terms of the size of the problem, n. Without stating what the problem is, and what is considered primitive (what is being counted as a unit of "time" or "space"), the order of growth doesn't have any meaning.

Questions

• I tell you that the procedure (λ (n) (+ n 1)) runs in O(n³) time. Am I on crack?
• If I ask you for a procedure that runs in Θ(log n) time and Θ(n) space, can you give me one? What about O(log n) time and O(n) space?
• Simplify these expressions:
  1. O(17)
  2. O(3n² + n/4)
  3. Θ(3³⁺ⁿ)
  4. Ω(n² log n + n²)
  5. O(1000000 log n)
  6. Θ(2ⁿ + n¹⁰⁰⁰)
  7. Θ(log₂₀ n/20)

What are the orders of growth (in time and space) of:

• Ordinary recursive factorial (sorry, I lied about it not coming up again)
• Iterative factorial
• church-inc
• church-add
• church-mul
• church-dec
• church=

The many faces of Fibonacci

Write a function that finds the nth Fibonacci number:

• in exponential time

• in linear time

• giving an approximate answer in constant time

• Hard: in logarithmic time