AMORTIZED ANALYSIS, It's types and applications.pptx

Ammortized analysis
Types
Applications

1. AMORTIZED ANALYSIS LET’S AVERAGE THE OPERATIONS

2. What happens when we have a costly operation that only occurs some of the time? Example: My array is too small. Let's enlarge it. Option 1: Increase array size by 10 Copy old array into new one Option 2: Double the array size Copy old array into new one We will now explore amortized analysis!

3. What is Amortized Analysis: Amortized analysis is a technique used in computer science and algorithms to analyze the average time complexity of an algorithm over a sequence of operations. Rather than analyzing the worst-case time complexity of individual operations. It provides a more accurate and realistic understanding of the overall performance of an algorithm. In amortized analysis, the cost of a costly operation is spread out over a series of cheaper operations, resulting in a lower average cost per operation. This approach allows for the possibility of occasional expensive operations as long as they are offset by a sufficient number of inexpensive operations.

4. Different methods of Amortized Analysis

5. Aggregate Method: The Aggregate Method is a straightforward approach to amortized analysis. It involves analyzing the total cost of a sequence of operations and dividing it by the number of operations to determine the average cost. This method provides an overall perspective of the average performance of the algorithm.

6. Accounting Method: The Accounting Method assigns each operation a specific "credit" or "charge" that represents the amortized cost. The credits are distributed across operations and used to cover the actual cost of expensive operations. This method ensures that the average cost of operations remains bounded and covers the worst-case scenarios.

7. Potential Method: The Potential Method assigns a potential function to the data structure being analyzed. The potential function measures the state or structure of the data at any given time. The amortized cost of an operation is the actual cost of the operation plus the change in potential caused by the operation. This method allows for a more fine-grained analysis of the cost associated with specific operations.

8. Dynamic Array Example: Let's consider an example of Dynamic Array to illustrate the methods of amortized analysis. Dynamic Array are resizable arrays that grow or shrink based on the number of elements. We can use the methods discussed to analyze the cost of resizing operations in dynamic arrays.

9. Aggregate Method Application: Using the Aggregate Method, we determine the total cost of resizing operations over a sequence of insertions and deletions. We divide the total cost by the number of operations to obtain the average cost per operation. This allows us to estimate the average time complexity of the operations.

10. Stretchy Array (version 1) StretchyArray : maxSize : positive integer (starts at 1) array: an array of size maxSize count: number of elements in array put(x): add x to the end of the array if maxSize == count make new array of size ( maxSize + 5) copy old array contents to new array maxSize = maxSize + 5 array[count] = x count = count + 1

11. Dynamic Array (version 2) DynamicArray : maxSize : positive integer (starts at 0) array: an array of size maxSize count: number of elements in array put(x): add x to the end of the array if maxSize == count make new array of size ( maxSize * 2) copy old array contents to new array maxSize = maxSize * 2 array[count] = x count = count + 1 June 20, 2012 CSE332: Data Abstractions 11

12. Performance Cost of put(x) In both stretchy array implementations, put(x)is defined as essentially: if maxSize == count make new array of bigger size copy old array contents to new array update maxSize array[count] = x count = count + 1 What f(n) is put(x) in O( f(n) )?

13. Performance Cost of put(x) In both stretchy array implementations, put(x)is defined as essentially: if maxSize == count O(1) make new array of bigger size O(1) copy old array contents to new array O(n) update maxSize O(1) array[count] = x O(1) count = count + 1 O(1) In the worst-case, put(x) is O(n) where n is the current size of the array!!

14. But… We do not have to enlarge the array each time we call put(x) What will be the average performance if we put n items into the array? O(?) Calculating the average cost for multiple calls is known as amortized analysis  

15. Amortized Analysis of StretchyArray Version 1 i maxSize count cost comments Initial state 1 5 1 0 + 1 Copy array of size 0 2 5 2 1 3 5 3 1 4 5 4 1 5 5 5 1 6 10 6 5 + 1 Copy array of size 5 7 10 7 1 8 10 8 1 9 10 9 1 10 10 10 1 11 15 11 10 + 1 Copy array of size 10 ⁞ ⁞ ⁞ ⁞ ⁞

16. Amortized Analysis of StretchyArray Version 1 i maxSize count cost comments Initial state 1 5 1 0 + 1 Copy array of size 0 2 5 2 1 3 5 3 1 4 5 4 1 5 5 5 1 6 10 6 5 + 1 Copy array of size 5 7 10 7 1 8 10 8 1 9 10 9 1 10 10 10 1 11 15 11 10 + 1 Copy array of size 10 ⁞ ⁞ ⁞ ⁞ ⁞ Every five steps, we have to do a multiple of five more work

17. Amortized Analysis of StretchyArray Version 1 Assume the number of puts is n=5k We will make n calls to array[count]=x We will stretch the array k times and will cost: 0 + 5 + 10 + … + 5(k-1) Total cost is then: n + (0 + 5 + 10 + … + 5(k-1)) = n + 5(1 + 2 + … +(k-1)) = n + 5(k-1)(k-1+1)/2 = n + 5k(k-1)/2 ≈ n + n 2 /10 Amortized cost for put(x) is  

18. Amortized Analysis of StretchyArray Version 2 i maxSize count cost comments 1 Initial state 1 1 1 1 2 2 2 1 + 1 Copy array of size 1 3 4 3 2 + 1 Copy array of size 2 4 4 4 1 5 8 5 4 + 1 Copy array of size 4 6 8 6 1 7 8 7 1 8 8 8 1 9 16 9 8 + 1 Copy array of size 8 10 16 10 1 11 16 11 1 ⁞ ⁞ ⁞ ⁞ ⁞

19. Amortized Analysis of StretchyArray Version 2 i maxSize count cost comments 1 Initial state 1 1 1 1 2 2 2 1 + 1 Copy array of size 1 3 4 3 2 + 1 Copy array of size 2 4 4 4 1 5 8 5 4 + 1 Copy array of size 4 6 8 6 1 7 8 7 1 8 8 8 1 9 16 9 8 + 1 Copy array of size 8 10 16 10 1 11 16 11 1 ⁞ ⁞ ⁞ ⁞ ⁞ Enlarge steps happen basically when i is a power of 2

20. Amortized Analysis of Dynamic Array00 Version 2 Assume the number of puts is n=2 k We will make n calls to array[count]=x We will stretch the array k times and will cost: ≈1 + 2 + 4 + … + 2 k-1 Total cost is then: ≈ n + (1 + 2 + 4 + … + 2 k-1 ) ≈ n + 2 k – 1 ≈ 2n - 1 Amortized cost for put(x) is  

21. Accounting Method Application Applying the Accounting Method, we assign a credit or charge to each resizing operation in the dynamic array. We distribute the credits across the insertions and deletions to cover the cost of resizing. This ensures that the average cost per operation remains bounded, even in worst-case scenarios.

22. Accounting Method Application We assign every operation a cost (Relative to i -the i th iteration) Any surplus goes to bank Idea: Need to overcharge for simpler operations Build up enough surplus to afford a more expensive operation later Challenge: Bank balance must always be 0 or greater

23. Potential Method Application: With the Potential Method, we assign a potential function to the dynamic array. The potential function reflects the difference in the size of the array and the number of elements it contains. The amortized cost of resizing operations is calculated as the actual cost plus the change in potential. This method provides a more detailed analysis of the dynamic array’s state and its impact on the cost of operations.

24. The Lesson With amortized analysis, we know that over the long run (on average): If we stretch an array by a constant amount, each put(x) call is O(n) time If we double the size of the array each time, each put(x) call is O(1) time