Lesson Plan - 6.001 SP04 - recitation 4

Orders of growth

project 1 due 6pm
project 2 out 6pm
no classes Mon, Tue virtual monday


definition
 f(n) = Theta(g(n)) ->  k1g(n) <= f(n) <= k2g(n), for n > n0
 f(n) = O(g(n)) -> f(n) <= kg(n), for n > n0

implications
 ignore constants

patterns
 (+/- n 1) - reduce problem by constant
 (/ n 2)   - scale problem by constant

Human Arithmatic:

n is number of digits

 6001
+6001
-----
12002

takes order n time, constant space (iterative - no deferred ops)

       6001
     * 6001   
-----------
       6001
      0000
     0000
  +36006   
-----------
   36012001

takes order n^2 time, n space (recursive - deferred ops)

micro-quiz!

how long in terms of the size of the number (not digits)?  log n

Micro Quiz solutions:
1)
(define (num-digits n)
  (if (= n 0)
      0
      (+ 1 (num-digits (quotient n 10)))))
O(n) time, O(n) space

2)
(define (mul-helper a b total)
  (if (= a 0)
      total
      (mul-helper (- a 1) b (+ total b)))) ; or (+ a -1) if picky
(define (slow-mul a b)
  (mul-helper a b 0))

O(n) time, O(1) space
; fibonacci two ways:
(define (fibbad n)
  (if (< n 2)
      n
      (+ (fibbad (- n 1)) (fibbad (- n 2)))))
; recursive, O((golden ratio)^n)

Problems:
1) Running Time O(n), space O(n)
2) Running Time O(n^2), space O(n)

(define (fibgood n)
  (define (helper current prev count)
    (if (= count 1)
	current
	(helper (+ prev current) current (- count 1))))
  (helper 1 0 n))
; iterative, O(n)

(define prime?
  (lambda (p)
    (define helper
      (lambda (n)
        (if (> n (sqrt p))
	    #t
            (if (divisible? p n)
		#f
		(helper (+ n 1))))))
    (helper 2)))
; iterative process
; assuming sqrt takes O(1) time, sqrt(n) * n