COMPSCI 61B Lecture Notes - Lecture 19: Branch Predictor, Computational Geometry
1 Jun 2017
School
Department
Course
Professor
Document Summary
If you get more than 100 points, you start earning gold points. see about. html for more. Extra credit due yesterday, but submit by 11:59 for no penalty. Key idea: use some subset of the entries of an array. Array resizing by multiplying by 2 is much more e cient than adding by 1. When the array inside the arraylist is full, double in size. Most add operations are constant time, but some are very expensive. Other models possible, e. g. can count array allocation. Analyses under these models yield the same results. This amortized total cost actually tops out, doesn"t go to in nity, so it is constant time on average. Amortized cost is a made up quantity, not a physical quantity. We can rigorously show by overestimating the constant time of each operation, and proving that resulting potential is never < 0 (cs 170)
