In this section, you will analyze minimum time needed to implement several operations on a Linked List and Array List. In your HW3Part3.pdf file, give the minimum required running time to execute each of the following operations in a doubly linked list with head and tail pointers, and Array List in the worst case, using Big-? notation, assuming n is the number of elements in the list. Following each expression, include a 1-2 sentence argument about why an algorithm to perform the given operation could not run faster than the bound you give. As above, full credit will be given only for tight Big-? bounds. That is, it is not sufficient to say that all operations take ?(l). This is trivially true for any piece of code. (Though in some cases this will be the tightest Big-Ohm bound). Example Question: Adding a value to the start of the list. Example Answer: Running time: Ohm(l). You have a pointer to the head node in the list, so adding an element involves creating a new node (which is not dependent on the length of the list), setting the links in the new node, and changing the values of the head references. This takes somewhere around 10 steps to perform, and 10 = Ohm(l). Example Question: Adding a value to the start of the array list. Example Answer: Running time: Ohm(n). You have to move everything over one cell to create a room for a new element. It will be done using a for loop that iterates through all elements. Since there are n elements in the list, it takes Ohm(n) to add a new element to the beginning of the array list. (Refers to both Linked list and Array List, so you need to have 10 answers. Making a copy of the list. Adding a value to the end of the list. Removing the first value from the list. Removing the last value from the list. Determining whether the list contains some value V.
1. Making a copy of the list
2. Adding a value to the end of the list
3. Removing the first value from the list
4. Removing the last value from the list
5. Determining whether the list contains some value V
Linked List:
1. Omega(n): you need to traverse all elements of the linked list and create a copy of each element and add to new list
2. Omega(1) : you just need to point New Node next to head node and assign head to new node
3. Omega(1) :you just need to point head of list to element next to head
4. Omega(n) : First you need to traverse till one node before last node and then make this node next to NULL
5. Omega(n) : Since you do not know where the give value will be in list. You need to traverse one by one all element from first node and check whether current node is equal to V or not
Array List:
1. Omega(n): you need to traverse all elements of the array list and create a copy of each element and add to new array list
2. Omega(1) : you just need to add new value at last of array list
3. Omega(n) : you need to move all elements from second to last one slot left
4. Omega(1) : You just need to decrease the size of array list, so the last element will be considered as deleted
5. Omega(n) : Since you do not know where the give value will be in list. You need to traverse one by one all element from first element and check whether current node is equal to V or not
Homework Sourse
