Queues (Feb 13)
Sorry, website's kinda behind lately because of A1 grading + thesis... will try to get it back up to speed at the end of reading week.
[circle dequeue methods][2KB](txt)
Amortized Cost (question 6)
The amortized cost is like an average cost. For example, the amortized cost of the add() function for n elements into an array, would be the sum of the individual costs of adding each element, divided by n. If there are 10 elements to be added, but the array is only size 8, then the first 8 adds will cost 1 unit. However, when we try to add the 9th element, the existing array has to be copied to a bigger array, meaning the 9th add operation will cost 8 units for copying the existing elements, plus 1 unit for adding the 9th element. The 10th element will just be 1 unit again, assuming we increased the array to at least size 10.
*operations are simplified, and assumed to cost just 1 unit of time
From above, we can see that the cost of an add() operation becomes much more expensive if we have to resize the underlying static array.
Case 1: Double the array whenever it is full.
We assume the cost of copying an element is just 1 unit. Every time the array is full, we double the size of it. When we double the size, we have to copy the existing elements.
Starting with an array of size 1, and adding n elements...
Current array size | Cost to copy existing elements | New array size |
1 | 1 | 2 |
2 | 2 | 4 |
4 | 4 | 8 |
8 | 8 | 16 |
... | ... | ... |
n/2 | n/2 | n |
As you can see, the total cost to copy the existing elements, until we reach array size n, is:
1+2+4+ ... + n/2 + n < 2n
We know the sum is less than 2n, because n is half of 2n, n/2 is half of n, etc. The way the values decrease in size guarantees that the total sum will never reach 2n.
With a total cost of 2n, and n add() operations, the amortized cost is 2n/n = 2, which is Θ(1).
Case 2: Incrase array size by a constant whenever it is full.
Let's say we increase by size by 5 every time the array is full.
This means that given n elements to add, we have to copy the existing array n/5 times. We know this because every five elements will fill up the array once, forcing it resize (therefore copy).
When we copy the existing array, the existing elements in in the order of n. To do this operation n/5 times, we get a total cost in the order of n2. Dividing the total cost by n add operations gives us an amortized cost of Θ(n).