Growth Factor
Consider a dynamic array-based implementation of Stack. The amortized cost of push
depends on the growth factor employed to expand (resize) the array.
Exercise If the array size starts at $1$, how expensive will it be to grow to $1$ million if we grow the array one element at a time?
Solution
When we call grow
in the push
method, if we grow the array by one (or few) elements, then the number of times we call "grow" linearly increases with the number of times we call "push."
The function grow
itself is a linear-time operation. So we have a situation that looks like $O(n) \times O(n)$, which gives us $O(n^2)$ quadratic runtime for $n$ "push" operations.
Another way to see this is that for one million push, the (computational) work performed by the "grow" operation (in total) will be as follows.
$$ 1 + 2 + \dots + 999999 = 499999500000 \approxeq \text{1 billion} $$
The above shows the $O(n^2)$ total runtime for $n$ "push" operations. The amortized cost of push
will then be $\frac{O(n^2)}{n}=O(n)$.
Exercise If the array size starts at $1$, how expensive will it be to grow to $1$ million if we double the size of the array each time we reach its capacity?
Solution
If we grow the array by doubling its size, the number of times we call grow
logarithmically increases with the number of pushes.
Let's say we start with an array of 1 element, and then we do $n$ push. The total work done is as follows.
$$ 1 + 2 + 4 + 8 + \dots + 2^{\lg n} = 2^{(\lg n) + 1} - 1 $$
The total above is calculated by adding up all the powers of two.
Note that $2^{\lg n} = n$ (recall $\lg n$ is $\log_{2} n$. Moreover, look at rule #7 of logarithm rules).
So we have the following:
$$ 2^{(\lg n) + 1} - 1 = \left ( 2^{(\lg n)} \times 2 \right ) - 1 = 2n - 1 \in O(n) $$
Thus the total runtime is $O(n)$ for $n$ "push" operations. The amortized cost of push
will then be $\frac{O(n)}{n}=O(1)$.
Dynamic arrays resize by a multiplicative factor, such as doubling in size, to avoid incurring the cost of resizing many times. That is, as $n$ elements are inserted, the values of increased capacities form a geometric progression.
Resources
- Wikipedia entry: Dynamic array -- Geometric expansion and amortized cost.