Amortized Analysis: Physicist's Method

Course video 11 of 60

In this module, we discuss Dynamic Arrays: a way of using arrays when it is unknown ahead-of-time how many elements will be needed. Here, we also discuss amortized analysis: a method of determining the amortized cost of an operation over a sequence of operations. Amortized analysis is very often used to analyse performance of algorithms when the straightforward analysis produces unsatisfactory results, but amortized analysis helps to show that the algorithm is actually efficient. It is used both for Dynamic Arrays analysis and will also be used in the end of this course to analyze Splay trees.

Über Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world
Earn a skill-based course certificate to apply your knowledge
Gain confidence in your skills and further your career