Problem Set 5

Questions to practice amortized analysis.

We'll cover the following

Question 1

A sequence of n operations are performed on a data-structure. The ith operation costs i if i is an exact power of k for some fixed integer k≥2 and 1 otherwise.

  • Use aggregate analysis to determine amortized cost per operation.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.