O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Amortization

To better understand the concept of amortization, let's look at a dynamic array. This is an array that would grow if there is no space to add a new element. We could do this as follows:

  1. Allocate a new array double the size of the current array.
  2. Copy all the elements from the current array to the new array.
  3. Make the new array the current array.

Here is a sample run of the algorithm depicted pictorially:

Amortization

This allocation and copying obviously incur O(n) cost once in a while. If most of the elements incur a O(1) cost, we should be fine though.

If you continue to trace the growth of this array, you will soon realize that the allocate/copy operations ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required