Consider a linked list data structure. Each node in the list contains a sorted array as its data So, this data structure consists of a linked list of sorted arrays If the first node is node 0, then node i's aray wil have length exactly 2. So, this is a linked list of sorted arrays, where each array is twice the size of the previous array Finally, every array is either completely, or completely empty. If you want to store 12 things in the data structure, there is exactly one way to do it: store 4 things at node 2, and 8 things at node 3 One way to think of it is this: if you want to store r things in the data structure, convert r to binary. If the ith (0-based) least significant bit is set, then that node's array is full, otherwise it is empty Here is how to insert: . Start at the 0th node If the current node is empty, place the data there, and you're done . Otherwise, merge (the function from mergesort) the current node's contents with the data you're trying to insert: now the current node is empty, and you're trying to insert twice as many things. Go to the next node, and return to the previous step in the algorithmm Answer the following questions (a) Explain how the find function would work, and show that it takes (log2n) worst-case runtime (b) Prove that the insert function takes (n) worst-case runtime (c) Analyze the amortized runtime for insert (d) Suppose you had a delete function implemented for this data structure (you don't have to figure out how to do this) How might the delete function negatively interact with your insert function's amortized runtime? Consider a linked list data structure. Each node in the list contains a sorted array as its data So, this data structure consists of a linked list of sorted arrays If the first node is node 0, then node i's aray wil have length exactly 2. So, this is a linked list of sorted arrays, where each array is twice the size of the previous array Finally, every array is either completely, or completely empty. If you want to store 12 things in the data structure, there is exactly one way to do it: store 4 things at node 2, and 8 things at node 3 One way to think of it is this: if you want to store r things in the data structure, convert r to binary. If the ith (0-based) least significant bit is set, then that node's array is full, otherwise it is empty Here is how to insert: . Start at the 0th node If the current node is empty, place the data there, and you're done . Otherwise, merge (the function from mergesort) the current node's contents with the data you're trying to insert: now the current node is empty, and you're trying to insert twice as many things. Go to the next node, and return to the previous step in the algorithmm Answer the following questions (a) Explain how the find function would work, and show that it takes (log2n) worst-case runtime (b) Prove that the insert function takes (n) worst-case runtime (c) Analyze the amortized runtime for insert (d) Suppose you had a delete function implemented for this data structure (you don't have to figure out how to do this) How might the delete function negatively interact with your insert function's amortized runtime
