Computational Modeling Fall 2008 For today, you should: 1) read your swappy book and write a summary/commentary 2) read Chapter 3 and think about what exercises you want to do (we'll start on Tuesday) Today: 1) quiz notes: order of growth analysis 2) finish your Chapter 2, if you haven't 3) work on Chapter 3 For next time you should: 1) work on Chapter 3, aim to finish next Tuesday 2) clean up the wiki, and get ready for book reports: identifying themes Q: should we do 1-2 more rounds with the swappy books? Quiz notes ---------- 1) The wikipedia page says O(n!) = O(n^n) If we interpret O(f) to be the set of functions that grow no faster than f, then this relationship claims that O(n!) and O(n^n) are the same set, which is FALSE. Actually, n! is in O(n^n), but n^n is not in O(n!). In other words, O(n!) is a subset of O(n^n) Proof sketch: write out n! and n^n as products and characterize their ratio. Corollary: O(n log n) =? O(n!) 2) Lookup in a BST is O(h), where h is the height of the tree. IF the tree is reasonably balanced, then h is O(log n), so lookup is O(log n). BUT in the worst case, h is O(n) and lookup is O(n). Which is the motivation for red-black trees. 3) A correct implementation of mergesort is O(n log n). Proof sketch: a) The number of levels of recursion is O(log n). b) The total amount of work at each level is O(n). HOWEVER: this implementation is broken, because merge is O(n^2) (because pop(0) is O(n)) def merge(t1, t2): ts = [] while t1 and t2: t = min(t1, t2) ts.append(t.pop(0)) ts.extend(t1) ts.extend(t2) return ts (BTW, I should have renamed "t" something like "winner") a) So what's the order of growth for the broken one? b) Write a correct version of merge.