(a) What is the big O of accessing the element at the middle position of an Arra
ID: 3883810 • Letter: #
Question
(a) What is the big O of accessing the element at the middle position of an ArrayList? (Or the middle two elements if the length is even.) Assume the ArrayList has n values.
(b) What is the big O of removing the last node of a doubly linked list having a tail reference? Assume the list has n nodes.
(c) What is the big O of adding to the end of a singly-linked list with no tail reference? Assume the list has n nodes.
(d) What is the big O of removing all occurrences of a given data item, x, from a doubly-linked list having a head reference and a tail reference. Assume the list has n nodes.
(e)This ADT is FIFO. (Do not ask what an ADT is. Obviously do not ask what FIFO is. This is a test and you are being tested to see if you know.)
Explanation / Answer
(a) O(1) => If arraylist is odd then arraylist.size()/2, if its even then (arraylist.size()/2)-1 and arraylist.size()/2
(b) O(1) => Can access the last element if tail reference is available.
(c) O(n) => we need to iterate with the help of head pointer till the tail and insert new node.
(d) O(n) => if there are n elements, we can iterate throught the list to remove all occurrence of data item x
(e) Queue => FIRST IN FIRST OUT which is abstract data type
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.