1David Evanshttp://www.cs.virginia.edu/evansClass 11: Golden Ages, Orders of Growth, and AstrophysicsCS150: Computer ScienceUniversity of VirginiaComputer Science2CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityAstrophysics• “If you’re going to use your computer to simulate some phenomenon in the universe, then it only becomes interesting if you change the scale of that phenomenon by at least a factor of 10. … For a 3D simulation, an increase by a factor of 10 in each of the three dimensions increases your volume by a factor of 1000.”• How much work is astrophysics simulation (in Θnotation)?Θ(n3)When we double the size of the simulation, the work octuples! (Just like oceanography octopi simulations)3CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityOrders of Growth0204060801001201401 2 3 4 5n3 n2 nsimplesortsimulatinguniversefind-best4CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityOrders of Growth02000004000006000008000001000000120000014000001 11 21 31 41 51 61 71 81 91 101simplesortsimulatinguniversefind-best5CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityAstrophysics and Moore’s Law• Simulating universe is Θ(n3)• Moore’s law: computing power doubles every 18 months• Tyson: to understand something new about the universe, need to scale by 10x• How long does it take to know twice as much about the universe?6CS150 Fall 2005: Lecture 11: Golden Ages and Complexity;;; doubling every 18 months = ~1.587 * every 12 months(define (computing-power nyears)(if (= nyears 0) 1 (* 1.587 (computing-power (- nyears 1)))));;; Simulation is θ(n3) work(define (simulation-work scale) (* scale scale scale)) (define (log10 x) (/ (log x) (log 10))) ;;; log is base e;;; knowledge of the universe is log 10 the scale of universe ;;; we can simulate(define (knowledge-of-universe scale) (log10 scale))Knowledge of the Universe27CS150 Fall 2005: Lecture 11: Golden Ages and Complexity(define (computing-power nyears)(if (= nyears 0) 1 (* 1.587 (computing-power (- nyears 1)))));;; doubling every 18 months = ~1.587 * every 12 months(define (simulation-work scale) (* scale scale scale)) ;;; Simulation is O(n^3) work(define (log10 x) (/ (log x) (log 10))) ;;; primitive log is natural (base e)(define (knowledge-of-universe scale) (log10 scale));;; knowledge of the universe is log 10 the scale of universe we can simulate(define (find-knowledge-of-universe nyears)(define (find-biggest-scale scale);;; today, can simulate size 10 universe = 1000 work(if (> (/ (simulation-work scale) 1000) (computing-power nyears))(- scale 1)(find-biggest-scale (+ scale 1))))(knowledge-of-universe (find-biggest-scale 1)))Knowledge of the Universe8CS150 Fall 2005: Lecture 11: Golden Ages and Complexity> (find-knowledge-of-universe 0)1.0> (find-knowledge-of-universe 1)1.041392685158225> (find-knowledge-of-universe 2)1.1139433523068367> (find-knowledge-of-universe 5)1.322219294733919> (find-knowledge-of-universe 10)1.6627578316815739> (find-knowledge-of-universe 15)2.0> (find-knowledge-of-universe 30)3.00560944536028> (find-knowledge-of-universe 60)5.0115366121349325> (find-knowledge-of-universe 80)6.348717927935257Will there be any mystery left in the Universe when you die?Only two things are infinite, the universe and human stupidity, and I'm not sure about the former. Albert Einstein9CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityInsert Sort(define (insertsort cf lst)(if (null? lst) null(insertel cf(car lst) (insertsort cf(cdr lst)))))(define (insertel cf el lst)(if (null? lst) (list el)(if (cf el (car lst))(cons el lst)(cons (car lst)(insertel cf el(cdr lst))))))insertsort is Θ(n2)10CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityDivide and Conquer• Both simplesort and insertsort divide the problem of sorting a list of length n into:– Sorting a list of length n-1– Doing the right thing with one element• Hence, there are always n steps– And since each step is θ(n), they are θ(n2) • To sort more efficiently, we need to divide the problem more evenly each step11CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityCan we do better?(insertel < 88 (list 1 2 3 5 6 23 63 77 89 90))Suppose we had procedures(first-half lst)(second-half lst)that quickly divided the list in two halves?12CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityInsert Halves(define (insertelh cf el lst) ;; assumes lst is sorted by cf(if (null? lst) (list el)(let ((fh (first-half lst))(sh (second-half lst)))(if (cf el (car fh)) ; before first half, put at beginning(append (cons el fh) sh)(if (null? sh) ; sh is null means fh has one element(append fh (list el))(if (cf el (car sh))(append (insertelh cf el fh) sh) (append fh (insertelh cf el sh))))))))(define (insertsorth cf lst)(if (null? lst) null(insertelh cf(car lst) (insertsorth cf (cdr lst)))))Same asinsertsortexcept usesinsertelh313CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityEvaluating insertelh> (insertelh < 3 (list 1 2 4 5 7))|(insertelh #<procedure:traced-<> 3 (1 2 4 5 7))| (< 3 1)| #f| (< 3 5)| #t| (insertelh #<procedure:traced-<> 3 (1 2 4))| |(< 3 1)| |#f| |(< 3 4)| |#t| |(insertelh #<procedure:traced-<> 3 (1 2))| | (< 3 1)| | #f| | (< 3 2)| | #f| | (insertelh #<procedure:traced-<> 3 (2))| | |(< 3 2)| | |#f| | (2 3)| |(1 2 3)| (1 2 3 4)|(1 2 3 4 5 7)(1 2 3 4 5 7)(define (insertelh cf el lst)(if (null? lst) (list el)(let ((fh (first-half lst))(sh (second-half lst)))(if (cf el (car fh)) (append (cons el fh) sh)(if (null? sh)(append fh (list el))(if (cf el (car sh))(append (insertelh cf el fh) sh) (append fh (insertelh cf el sh))))))))Every time we call insertelh, the lengthof the list is approximately halved!14CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityHow much work is insertelh?Suppose first-half and second-half are θ(1)(define (insertelh cf el lst)(if (null? lst) (list el)(let ((fh (first-half lst))(sh (second-half lst)))(if (cf el (car fh)) (append (cons el fh) sh)(if (null? sh)(append fh (list el))(if (cf el (car sh))(append (insertelh cf el fh) sh) (append fh(insertelh cf el sh))))))))Each time we callinsertelh, the size oflst halves. So, doublingthe size of the list only increases the number ofcalls by 1.List Size Number of insertelh applications1 12 24 38 416 515CS150 Fall 2005: Lecture 11: Golden Ages and ComplexityHow much work is insertelh?Suppose first-half and second-half are θ(1)Each time we callinsertelh, the size oflst halves. So, doublingthe size of the list only