Amortized Analysis: Aggregate Method

Understanding the Total Cost of a Sequence of Operations UsingAmortized Analysis A technique for calculating the overall cost of a series of actions is amortizedanalysis. It is a technique for considering the average cost of each operationrather than just the highest possible cost. Instead of only concentrating on theworst case scenario, this gives us a more nuanced perspective of the overall costof a set of activities. This article will define amortized analysis and examine one specific approach ofperforming it. We'll also examine the aggregate way of amortized analysis inmore detail, using a dynamic array as an illustration. Amortized Cost: What Is It? The cost of a series of operations divided by the quantity of operations is theamortized cost. It is comparable to the amortized cost concept in finance, whereyou set aside money each month to pay for a significant expense like a car. Youcan understand the expense more accurately if it is broken up into smaller,easier to handle payments. If a car costs $6,000, for instance, you could save $100 every month for fiveyears to pay for it. The car costs $100 a month to amortize, whereas theworst-case monthly cost is $6,000. Instead of only considering the worst casescenario, the amortized cost gives us a more complex picture of the cost of asignificant expense. The Aggregate Amortized Analysis Method According to the aggregate method of amortized analysis, we can use theamortized cost definition to directly calculate the amortized cost. With thisapproach, we examine the price of each operation in turn before calculating theoverall price. The amortized cost of a single operation is then calculated bydividing the total cost by the number of operations. Dynamic Array Illustration Let's examine the amortized analysis aggregate approach using a dynamic arrayas an illustration. Starting with a blank array, we'll make n calls to PushBack.We'll calculate the amortized cost of a single PushBack call.

Although a call to PushBack has an O(n) worst-case time, let's define c[i] as thecost of the ith insertion. The costs from c[1] through c[n] are what we'reinterested in. Since we must write the i[i]th] element we are adding to the array,c[i] is obviously 1. If our capacity is exhausted, which occurs if the size is equal to the capacity, wemust resize the array. If the previous insertion completely filled it, making it afull power of two, then this occurs. Let's assume that the array has a capacity of 8, and that 8 calls to PushBack aremade, filling the array. Resizing costs O(n), yet a single call to PushBack costsO after amortization (1). This is due to the fact that the cost of resizing the arrayis divided by the quantity of PushBack calls, resulting in a lower cost per call. A useful method for determining the overall expense of a series of procedures isamortized analysis. This gives us a more nuanced perspective of the entire costsince it enables us to look at the average cost of each operation rather than justthe worst case cost.