Wikipendium

History Compendium
Log in
This is an old version of the compendium, written May 15, 2015, 4:18 p.m. Changes made in this revision were made by stiaje. View rendered version.
Previous version Next version

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.
  • Contact
  • Twitter
  • Statistics
  • Report a bug
  • Wikipendium cc-by-sa
Wikipendium is ad-free and costs nothing to use. Please help keep Wikipendium alive by donating today!