\section*{Question 1: Amortize Analysis} Consider the following data structure of…
- User
\section*{Question 1: Amortize Analysis} Consider the following data structure of Dynamic Array which consists of an array with initial size of 1 together with a variable "size" denoting the number of slots that contain data now. Insert() and Delete() are supported functions. Insert() will insert an element into the first empty slot in the array while Delete() will delete the element in the last occupied slot of the array. In order to make the whole data structure adaptable to size, Shrink() and Expansion() will be triggered by Delete() and Insert() respectively. In other words, if after Insert(), the array is full, then a new array with double size will be created and the contents in the old array will be copied to the new array one by one; If after delete(), the array has less than slots being occupied by numbers, then a new array with half size will be created and the contents in the old array will be copied to the new array one by one (No shrinking will be done if the array has size 2).
\begin{enumerate} \item (5 marks) What is the worst case running time for Insert() if the array size is n ? \item (5 marks) What is the amortized running time for a sequence of and Delete() operations? \item (5 marks) Give your proof for the above amortized running time. \end{enumerate}
- Assistant
Question 1: Amortize Analysis
Part 1: Worst-Case Running Time for
Insert()When Array Size is nAnswer:
The worst-case running time forInsert()when the array size is n is O(n).Explanation:
- In the typical
Insert()operation without resizing, inserting an element takes O(1) time. - However, if the array is full after the
Insert(), theExpansion()operation is triggered:- A new array with double the current size is allocated.
- All existing elements (n elements) are copied to the new array, which takes O(n) time.
Therefore, in the worst case—when resizing is required—the
Insert()operation runs in linear time relative to the size of the array, i.e., O(n).
Part 2: Amortized Running Time for a Sequence of n
Insert()andDelete()OperationsAnswer:
The amortized running time for a sequence of nInsert()andDelete()operations is O(1) per operation.
Part 3: Proof of the Amortized Running Time
Answer:
We can use the Accounting Method to prove that the amortized running time is O(1) per operation.Proof Using the Accounting Method:
-
Assigning Costs:
- Regular Operations (
Insert()without resizing andDelete()without shrinking):- Actual cost: O(1)
- Assign an amortized cost of $3 per operation.
- Resizing Operations (
Expansion()andShrink()):- Expansion:
- Cost to double the array: O(n)
- Number of elements to copy: n
- We have already assigned $3 to each of the n
Insert()operations that led to the expansion, totaling $3n, which is sufficient to cover the O(n) cost of copying.
- Shrink:
- Cost to halve the array: O(n)
- Number of elements to copy: n
- Similarly, the previously assigned coins cover the cost.
- Expansion:
- Regular Operations (
-
Charging Scheme:
- Each
Insert()andDelete()operation is charged $3, which:- Pays for the actual operation cost ($1).
- Saves $2 for potential future resizing costs.
- Each
-
Total Cost Analysis:
- For n operations, total amortized cost is O(n).
- Actual cost is also O(n) since resizing does not occur on every operation.
-
Conclusion:
- Since the amortized cost per operation remains constant (O(1)), the sequence of n
Insert()andDelete()operations has an amortized running time of O(1) per operation.
- Since the amortized cost per operation remains constant (O(1)), the sequence of n
Summary:
- Worst-Case Running Time for
Insert()when array size is n: O(n) - Amortized Running Time for n
Insert()andDelete()Operations: O(1) per operation - Proof: Utilized the Accounting Method to demonstrate that each operation can be charged a constant amortized cost, ensuring that the overall amortized cost remains linear in the number of operations.
- In the typical