If the set of stack operations included a MULTIPUSH operation, which pushes 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 push operation. Since one MULTIPUSH needs Θ(k)time, performing n MULTIPUSH operations, each with k elements, would take Θ(kn)time, leading to amortized cost of Θ(k).
Show that if a DECREMENT operation were included in the k-bit counter example, n operations could cost as much as theta(nk) time.
In the worst case, going from 1[k-1 0's] (ie. 1000 -> 0111) takes k flips. Could do any sequence of increment and decrement from 1000 -> 0111 -> 1000 -> 0111 (n times), which is theta(nk).
A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation.
Look at a sequence of n operations. Let k = floor(lg(n)). All operations cost equal to 1 + 2 * (1 - 2^k) / (1 - 2) + n - k - 1 = 2 * 2^k + n - k - 2 = O(n), than each operation cost equal to O(n) / n = O(1).