Amortized Analysis
For this assignment, write all time complexities in the form \(O([k \rightarrow k])\), define what each of your variables represent, and do not use \(n\) as a variable. Some examples of incorrect time complexities are: \([k \rightarrow k]\), \(O[k \rightarrow k]\), or \(O([k])\). Be sure to explain your reasoning behind each answer.
1 Flexible Arrays
insert elements at one end.
get the kth element.
Arrays (known as vectors in some languages) support accessing elements in constant time, but are fixed in size. However, the fixed size of arrays is a major limitation. Once an array is full, we can no longer insert elements.
makeFlexibleArray(): |
currentArray = new array[1] |
nextUnusedIndex = size of currentArray |
|
insertAtEnd(elem): |
if nextUnusedIndex > size of currentArray: |
newArray = new array[size of currentArray + 1] |
copy each element of currentArray to newArray |
nextUnusedIndex = size of currentArray + 1 |
currentArray = newArray |
insertAtEnd(elem) |
else: |
currentArray[nextUnusedIndex] = elem |
nextUnusedIndex = nextUnusedIndex + 1 |
|
get(k): |
get kth element of currentArray |
What is the worst case time complexity of makeFlexibleArray? insertAtEnd? get?
Is the amortized complexity of a sequence of \(k\) insertAtEnd operations any better? Assume that you start with the array of size 1.
2 Expanding Flexible Arrays
makeFlexibleArray(): -- unchanged
get(k): -- unchanged
insertAtEnd(elem):
ONLY change is
newArray = new array[size of currentArray + 1]
is replaced by
newArray = new array[size of currentArray * 2]
Assume that you start with an empty array. What is the amortized cost per operation of \(k\) insertAtEnd operations?
3 Shrinking Flexible Arrays
deleteLast():
delete last element of currentArray
When the array is half-full, shrink its size to half of what it was.
When the array is one-fourth full, shrink its size to half of what it was.
Answer the following question:
Which option is more efficient, and why? Give an example of a sequence of insertions and deletions with the corresponding amortized analysis to support your claim.
4 Cascading Arrays
Insert an element.
Determine whether a given element is in the structure.
One way to do this is to keep an array of elements in sorted order. Constant time access allows us to quickly search for elements using a binary search in \(O([k \rightarrow log k])\) time, but inserting elements is slow, \(O([k \rightarrow k])\), due to the requirement that the array remain sorted: when we add an element, all the elements after it in order must be shifted one array index to the right.
Array 0: [3] |
Array 1: [1, 6] |
Array 2: [_, _, _, _] |
Array 3: [2, 5, 7, 8, 10, 12, 20, 42] |
To insert an element, we first create an array of size \(1\) containing only that element. Then we iterate through the list of arrays, starting with the smallest. If array \(k\) is empty, we replace it with the full new array and we are done. Otherwise, we merge array \(k\) into the new array, doubling its size. Then we set array \(k\) to be empty and move on to array \(k + 1\).
Array 0: [_]
Array 1: [_, _]
Array 2: [1, 3, 4, 6]
Array 3: [2, 5, 7, 8, 10, 12, 20, 42]
makeSortedDict(): |
listOfArrays = empty |
search(elem): |
foreach array in listOfArrays: |
binary search for elem in array |
insert(elem): |
newArray = [elem] |
foreach array in listOfArrays: |
if array is empty: |
replace array with newArray in listOfArrays |
return |
else: |
newArray = merge array with newArray |
array = empty |
add newArray to end of listOfArrays |
Answer the following questions:
What is the time complexity of search?
Assume that you start with an empty array. What is the amortized cost per operation of \(s\) insert operations?
Can you think of a data structure you already know that provides this functionality with a better time complexity? Naming the structure is fine; we don’t expect a detailed response.
5 Handing In
Please turn in a hard copy of your answers for each of the questions, cleanly broken up and labelled by section. You can turn in your homework into the cs019 handin box on the second floor of the CIT, just outside the Fishbowl. Please do not hand-write your analyses unless your writing is extraordinarily legible; the burden of legibility is on you, not our responsibility. Please submit on letter-sized paper with all mathematical content formatted appropriately. Put your name and login at the top of each page.