Amortized Cost in Data Structure

Question

Hi How can I find the amortized cost of constant increment in data structure for example, if the increment of size of the array by 1000 ie ( from N -> N+1000) every time if its overflow

and also by fixed factor ie from ( N -> 7*N)

I get an idea how it works when it's doubled like 1 -> 2, 2-> 4 but I am having a hard time getting an idea about constant increment

Answer 1

Appending to a list that uses a constant-size resizing strategy takes O(n) time amortized.

Let's say you have n append operations to a list for some arbitrary positive integer n.

Then, for every 1000th operation, you need to resize the underlying array, which requires copying m elements, where m is the size of the list at the time of resizing.

The total costs of resize operations can be expressed as 1000 + 2000 + 3000 ... [(n // 1000) * 1000]. Using the formula for the summation of the first n natural numbers, we can rewrite this as 1000 * (n // 1000) * (n // 1000 + 1) / 2 --> O(n^2), so the amoritized cost of appending to a list using the resizing strategy you mentioned is O(n).