please answer both. 2. In order to properly answer the last question, several as

Question

please answer both.

2.

In order to properly answer the last question, several assumptions may have been made. What did you assume? For example, did write your Big-Oh in terms of array resizing? Or did you assume that the array didn't need to resize?

n this unit, we introduced three kinds of list ADTs, including the actual indexed list ADT provided by Java (see table). There are two primary ways such a table could be implemented: arrays and linked structures. Based on your knowledge of these data structures, complete the following table Method void add(E element) voir adol ni indlex, elemeni eris elementahe index. E get(int index) void remove(int index) void remove(E object) void ssifint index, l elermenij ces elemeni ai the indx int size) On the table, make bold the operations which have a different order. Give a brief explanation for the difference below. Description rray Big-Oh Linked Big-Oh Adds element to the end of the list. Returns element at the index. Removes element at the index. Removes first occurrence of the object. Returns number of elements in the list.

Explanation / Answer

1)Adding Element at the end of list:

1.a.ARRAY:Actually adding the element in array is not possible because arrays are static in case if you created the dynamic array then at the time of creation if you maintained any pointer then adding element end is takes O(1);if not then it takes O(N) because we need to traverse entire array.

1.b.LINKED LIST:Same thing applies to linked list but here linked list are dynamic we can create the list using dynamic memeory allocation.

2)Insert Element:

2.a.ARRAY:Same thing if array is static not possible if it is dynamic then the worst case we can insert at end so O(N)

2.B.LINKED LIST:here also insertion can be done at the end of linked list so we need to traverse entire list so O(N)

For the remaining problems also we can apply same analogy because we want to perform all operations at the end of list so we need to traverse so worst case O(N) it will take apart from O(N) just we need to small opetations with the nodes of the links.those all minor modifications and they all take O(1) so therefore Time Complexity is O(N)

FOR LAST PROBLEM IF WE WANT TO FIND THE SIZE OF LIST NO OTHER GO IF LIST END TILL WE NEED TO COUNT AND FINALLY WE WANT TO RETURN THE NUMBER OF ELEMENTS SO DEFINITELY THEY WILL TAKE o(n) Time.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.