CSE 250 Lecture Notes - Lecture 15: Operator Overloading
4 Mar 2017
School
Department
Course
Professor
Document Summary
Our cost for each insertion is o(1) (since we have nothing to shift right). Doubling occurs every time out number has the form 2i: costs o(2i): we have to double log i times. How much does everything cose: total cost of inserting n items to back of vector, suppose n = 2k + 1, for some positive int k. Insertion costs: n operations, o(1) each: (cid:4666)(cid:883)(cid:4667) Runtime is amortized o(1): silly to say push_back has a runtime of o(n), but have the cost of inserting n items always results in runtime of o(n) Amortized used to describe runtime over the long run reserve only called to double size roughly log(n) times, i. e. , very infrequently: not quite the same as the average case. We would like to maintain the array access through array[index: c++ allows operator overloading, this allows us to redefine operators for our class template
