CS 225 Lecture Notes - Lecture 17: General Idea, Linked List
2 Oct 2016
School
Department
Course
Professor
Document Summary
Stack array based implemenetation: (what if array fills?) analysis holds for array based implementations of lists, stacks, queues, // new piece of data, but array is full. General idea: upon an insert (push), if the array is full, creates a larger space and copy the data into it. We examin 2: create new bigger array certain amount, copy data from old to new, input new data, delete old, rename new array to old array. // give the opporunity to increase the size by a. Stack array based implementation: (what if array fills?) copy cost = c + 2c + 3c + The final cost is about (n-c)/c amount of costs. = sum(i=1) (n/c -1) {ci} // c is a constant. It takes n^2 to do n pushes o(n^2) On average it will be o(n^2/n) = o(n) purposes o(n^2) Stack array based implementation: (what if array fills?) copy cost: 1 + 2 + 4 +
