Growth Factor

  • Elaborate on the importance of array growth factor to maintain amortized constant time push operation.

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 $\Omicron(n) \times \Omicron(n)$, which gives us $\Omicron(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 $\Omicron(n^2)$ total runtime for $n$ "push" operations. The amortized cost of push will then be $\frac{\Omicron(n^2)}{n}=\Omicron(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 \Omicron(n) $$

Thus the total runtime is $\Omicron(n)$ for $n$ "push" operations. The amortized cost of push will then be $\frac{\Omicron(n)}{n}=\Omicron(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