Search code examples
amortized-analysis

Amortization complexity when resizing arrays by a constant?

I know that when you resize an array by a scalar (like doubling the length of the array, then copying all elements into the new big array) the amortized time complexity is O(1).

But why is it the case that when you do it with a constant (say, resizing it by +10 each time) not O(1) as well?

Edit: https://www.cs.utexas.edu/~slaberge/docs/topics/amortized/dynamic_arrays/ this site seems to explain it, but I am very confused on the math. Where does big $N$ come from? I thought we were dealing with k?

Solution

  • If every kth consecutive insertions cost as much as the number of elements that are already in the array (denote by n+N*k where n is the initial size of the array) then you got sequences of this type:

    1. n O(1) Operations
    2. Expensive operation of O(n)
    3. k O(1) Operations
    4. Expensive operation of O(n+k)
    5. k O(1) Operations
    6. Expensive operation of (n+2k)
    7. k O(1) Operations
    8. Expensive operation of O(n+3k)

    See where this is going? each expensive insertion happens every k insertions (expect first time) and costs as the current number of elements.

    This means that after, lets simplify, n+A*k insertions we had A copies of n elements, and also we had A-1 copy of the first set of k elements, A-2 copies of the second set of k elements, and so on..

    This sums up to O(An + A^2 * k). And because we did n+Ak, we can divide to get amortized cost.

    This gives us (An + A^2 * k)/(n+Ak)=A

    So, this implies that we are amortized dependent in this array on the NUMBER OF INSERTIONS, which is bad because we won't be able to state that this array, does a constant work in average.