17.1.md

17.1-1

If the set of stack operations included a $\text{MULTIPUSH}$ operation, which pushses $k$ items onto the stack, would the $O(1)$ bound on the amortized cost of stack operations continue to hold?

No. The time complexity of such a series of operations depends on the number of pushes (pops vice versa) could be made. Since one $\text{MULTIPUSH}$ needs $\Theta(k)$ time, performing $n$ $\text{MULTIPUSH}$ operations, each with $k$ elements, would take $\Theta(kn)$ time, leading to amortized cost of $\Theta(k)$.

17.1-2

Show that if a $\text{DECREMENT}$ operation were included in the $k$-bit counter example, $n$ operations could cost as much as $\Theta(nk)$ time.

The logarithmic bit flipping predicate does not hold, and indeed a sequence of events could consist of the incrementation of all $1$s and decrementation of all $0$s; yielding $\Theta(nk)$.

17.1-3

Suppose we perform a sequence of $n$ operations on a data structure in which the $i$th operation costs $i$ if $i$ is an exact power of $2$, and $1$ otherwise. Use aggregate analysis to determine the amortized cost per operation.

Let $n$ be arbitrary, and have the cost of operation $i$ be $c(i)$. Then we have,

$$ \begin{aligned} \sum_{i = 1}^n c(i) & = \sum_{i = 1}^{\left\lceil\lg n\right\rceil} 2^i + \sum_{i \le n \text{ is not a power of } 2} 1 \\\ & \le \sum_{i = 1}^{\left\lceil\lg n\right\rceil} 2^i + n \\\ & = 2^{1 + \left\lceil\lg n\right\rceil} - 1 + n \\\ & \le 2n - 1 + n \\\ & \le 3n \in O(n). \end{aligned} $$

To find the average, we divide by $n$, and the amortized cost per operation is $O(1)$.