;; Don't forget to load long-sent early!!
(define-macro (utime form)
(let* ((t1 (butlast (exec "precisetime")))
(r (eval form))
(t2 (butlast (exec "precisetime"))))
(- t2 t1)))
;;
;; Today: how does the running time of a program (or single proc)
;; vary with the size of the input to the program?
;;
;; From Thursday
(define (by-ones a b)
(if (> a b)
(se)
(se a (by-ones (+ 1 a) b))))
(define 10-sent (by-ones 1 10))
(define 33-sent (by-ones 1 33))
(define 34-sent (by-ones 1 34))
(define 50-sent (by-ones 1 50))
(define 100-sent (by-ones 1 100))
(define 1000-sent (by-ones 1 1000))
;; How can the running time vary?
;; Choice 1: doesn't change
(define (second se)
(first (bf se))) ;; assume first and bf are constant time
(utime (second 10-sent))
(utime (second 33-sent))
(utime (second 50-sent))
(utime (second 100-sent))
(utime (second 1000-sent))
;; The running time of second doesn't change with the size of the
;; sentence. We say 'second runs in CONSTANT TIME'.
;; first, bf, are constant time algorithms.
;; choice 2: running time grows with size of input
(define (square x) (* x x))
(define (squares sent)
(if (empty? sent)
(se)
(se (square (first sent))
(squares (bf sent)))))
(utime (squares 10-sent))
(utime (squares 33-sent))
(utime (squares 34-sent))
(utime (squares 50-sent))
(utime (squares 100-sent))
(utime (squares 1000-sent))
;; linear since we go 'down the list'
;; choice 3: as polynomial (degree > 1)
;; Example: cartesian product
(define (prepend-every wd sent)
(if (empty? sent)
'()
(se (word wd '- (first sent))
(prepend-every wd (bf sent)))))
(prepend-every 'foo '(1 2 3))
(define (product se1 se2)
(if (empty? se1)
'()
(se (prepend-every (first se1) se2)
(product (bf se1) se2))))
(product '(a b c) '(1 2 3))
(utime (product 10-sent 10-sent))
(utime (product 33-sent 33-sent))
(utime (product 34-sent 34-sent))
(utime (product 50-sent 50-sent))
;; roughly quadratic:
;; access each element of se1 once, and, for each of those
;; access each element of se2 once -- each of those accesses
;; size 1-> 1 access,
;; size 2-> 4 accesses,
;; size 3-> 9 accesses
;;
;; n^2 running time!
;; n^10000
;; Choice 4: exponential!
(define (fib n)
(if (< n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))
(utime (fib 15))
(utime (fib 20))
(utime (fib 21))
(utime (fib 22))
;; fib 20 = X accesses
;; fib 21 = 2 X accesses
;; fib 22 = 2*fib21 = 4X accesses
;; doubles for each added input
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Peer Instruction: Think of a simple
;; algorithm that runs in a time other
;; than what we've seen and other than
;; in the reader ...
;;
;; Nah-
;;
;;
;; Re-write product using only HOP!
;; notice: Just two composed everys:
(define (prepend-every wd sent)
(every (lambda (y) (word wd '- y)) sent))
(define (product se1 se2)
(every (lambda (x) (prepend-every x se2))
se1))
(product '(a b c) '(1 2 3))
;; So, hook em up:
(define (product se1 se2)
(every (lambda (x)
(every (lambda (y)
(word x '- y))
se2))
se1))
(product '(a b c) '(1 2 3))
;; Exam-level question!
;;
;;
;; Math behind orders of growth:
;;
;;
;; we say f(x) is BigOh(g(x) iff
;; for all x great than some fixed k,
;; and for some fixed c,
;; f(x) <= c1*g(x)
;;
;; In English: Past a certain point, f is bounded
;; from above by g.
;; second is 0(1) : c= 15 or so
;; squares is 0(N)
;; product is 0(N*N)
;; fib is 0(2^N)
;; by the way, second is also 0(2^n)
;;
;; we say f(x) = BigTheta (g(x) iff
;; f = 0(g) and g = 0(f)
;;
;; Whole bunch of others:
;; little-oh, little-theta
;; Complex running times:
;; What is the running time of every?
(define (my-every fn sent)
(if (empty? sent)
'()
(se (fn (first sent))
(my-every fn (bf sent)))))
;; Well, ...
(every (lambda (x) (* x 2)) 10-sent)
(every (lambda (x) (by-ones 1 x)) 10-sent)
;; In first case, fn is 0(1) -> every = 0(N)*0(1)
;; (0(N) 'absorbs' 0(1) in constant!)
;;
;; In second case, fn is 0(N) -> every = 0(N)*0(N)
;; Absorption again? No!
;; 0(N*N) = 0(N^2)
;; In general, every = 0(N*fn)
;; If time: graph em!
;; Families:
Easy
----
1
log n
sqrt(n)
N
Exmaples: Searching, selecting, mapping, etc.
Medium
------
N log N
N^2
N^c
Examples: Sorting, matrix multiply,
Intractible:
------------
x^n
n!
n^n
Examples: The np-hard class, TSP.