TDT4125: Algorithm Construction, Advanced Course (2015)
# Amortized analysis
## Aggregate Analysis
## Accounting method
## Potential method
17.1-1
A multipush operation multipush(stack, n) is teta(n) cost.
A push operation is O(1)
A pop operation is O(1)
A MultiPop is min(S, k)
A MultiPush is k
Multipush is amortized over the k elements pushed, which gives it an amortized cost of teta(k) / k per element pushed, or Teta(1).
N combinations of push, pop, multipop, and multipush (All O(1) amortized) gives us O(n) / n = O(1).
17.1-2
If we allow a decrement operations, we allow for the line of operations consisting of
maxint + 1 - 1 + 1 - 1 + 1 -1.
Maxint +1 involves flipping all the 1-bits to 0, and MinInt + 1 the converse.
This makes each operation Theta(k), resulting in Theta(n*k) as there are no other operations to amortize the cost over.
17.1-3
The total cost for n operations would be bounded by SUM(1..n)(1) + SUM(1..floor(log(n)))(2**i).
This is bounded by n + 2n = O(n). Over n operations, this becomes O(n) / n -> O(1) amortized cost.
17.2-1
At worst, we will need k credits at a copy state. Between two copies, there will be k push or pop operations.
By making push and pop operations pay for themselves, as well as one extra credit, k push and pop operations will have left k * 1 credits on the stack when the next copy comes around, guaranteeing that all copy operations can be performed.