The traditional analysis Thus far, when we've analyzed algorithms it's been one operation at a time. So let's consider a single operation in the sequence of n operations. Obviously, the worst case is that we've done n-1 pushes, and then the last thing we do is multipop(n-1). This single operation will then take Θ(n) time. So, we have a series of n operations with O(n) cost, for a total time requirement of O(n^2). Hopefully you rebel at this, saying "Yes, it is O(n^2), but it can't really take that long! You can't have an expensive multipop operation without a whole bunch of inexpensive pushes coming first!"
Amortized analysis Amortized analysis is a bit different. It examines the worst case average cost of an operation in a sequence of n operations. Thus, instead of analyzing each operation in isolation, it analyzes operations in the context of a sequence of operations. This sometimes allows us to get a better idea of the true complexity of a task. In the multipop case we'll analyze the total cost of a sequence of n operations, and then take the average over all n operations to arrive at our amortized time per operation. Obviously, each object on the multistack gets pushed exactly once, and popped no more than once. So we have at most two "steps" for each object that finds its way onto the stack. In a sequence of n operations, clearly at most n objects get pushed onto the stack. Thus, we have at most 2*n "steps" in a sequence of n operations, i.e. n operations take Θ(n) time. Thus, on the average, each operation takes Θ(n)/n = Θ(1) in the worst case! Using amortized analysis we see that multipop operations take constant time ... in the amortized sense.
So, the amount we pay for each operation is fixed, and
it is the amortized cost of the operation. The number
of computational units actually required for a particular
instance of that operation being performed is the
actual cost of the operation. For example,
we'll show that
the amortized cost of a
multipop(k)
operation on a stack of
n elements is constant
whereas the actual cost varies depending on the
values of k and n.
The trick with the accounting method is to fix an amortized cost for each operation, and show that the actual cost of a sequence of M operations does not exceed M times the amortized cost. You overpay for the operations with very small actual cost, and the credit you build up pays for the occasional operation with large actual cost.
Operation Actual Cost Amortized Cost ----------------------------------------------- push 1 CU 2 CU pop 1 CU 0 CU multipop(k) min(k,s) ______ 0 CU \__| size | | of | | Stack| ------ We want to prove that the "balance" B in our computational account is always greater than or equal to zero, since this means out amortized payments always suffice to cover our actual costs. We will do this by proving that B >= S after every operation, where B is the balance and S is the size of the stack. 1) Initially both B and S are 0, so B >= S is true 2) Assume B >= S and we perform an operation resulting in new balance B' and new stack size S'. We'll show that regardless of which operation is performed, B' >= S' operation is a push so S' = S + 1 ------------------ B >= S B + 2 - 1 >= S + 2 - 1 B' >= S + 1 >= S' operation is a pop so S' = S - 1 ------------------ B >= S B + 0 - 1 >= S + 0 - 1 B' >= S - 1 >= S' operation is a mulitpop(k) so S' = S - min(k,S) ------------------ B >= S B + 0 - min(k,S) >= S + 0 - min(k,S) B' >= S - min(k,S) >= S'
> ./parse <html> <head> <title> </title> <body> <img> <b> <a> </a> </b> <p> <hr> </p> </body> </html> 6 matched and 3 unmatched tagsAssuming the maximum tag length is a small constant, let's analyse the algorithm in terms of n, the number of tags in the input. Essentially, the running time is dominated by the outer while loop, which loops over each tag, and its body, in which we either push, or loop through a bunch of pops. So, each time through the outer while loop, you either push or do multiple pops --- i.e. do a multipop. Our amortized analysis told us that the amortized costs, across a sequence of operations, of push and multipop are both Θ(1). So in analyzing our algorithm we can treat those operations as if they took constant time which, individually, we actually know they don't! So, the running time, assuming we don't break out of the while loop early, is n*Θ(1), which is Θ(n).