Assume the following lists each implement the List ADT as efficiently as possibl

Question

Assume the following lists each implement the List ADT as efficiently as possible for their given data structure specified below: L1 is an array list that has been filled with P items. L2 is a singly-linked chain of nodes with only a head reference and has been filled with Q items, L3 is a singly-linked chain of nodes with both head and tail references and has been filled with R items, o L4 is a circular, doubly-linked chain of nodes with only a head reference and has been filled with S items. What is the worst-case time complexity for each code fragment below? Express the complexity using "Big-O" notation and making sure to use the appropriate variables that correspond with the problem size. Assume printing output, doing .equals(), and constructing a new item take constant time.

Explanation / Answer

A. L4 is a circular, doubly linked list which allows us to move in eighter direction from a given node. Therefore adding an item at the end or to the front has worst complexity of O(1).

B. Let's break the if condition and determine the complexity of each expression

When L3.contains(item) fails and L3.size() > L2.size() success: O(R) + O(1) + O(1) + O(1) = O(R) i.e. O(R)

C.

Only one of 1, 2 or 3, 4 can happen therefor MAX(O(P), O(Q)).

D. Whenever we remove 0th indexed element it will require us to move all remaining by one to left. Therefore P - 1 shifts on first removal. We are removing elements till array becomes empty, hence

(P - 1) + (P - 2) + (P - 3) + .. + 1 = [ (P - 1) (P) ] / 2

Hence complexity = O((P2 - P) / 2) = O(P2)

E. For each addition of linked list to end we need to traverse the list costing Q. For N elements it will be Q * N when elements are inserted to end.

If elements are inserted to from it will be only O(N) as we don't have to traverse whole list.

F. To delete an item from end of we need to traverse list even though we have tail pointer. Because we don't have back link from last node to traverse back. Hence deleting each item from back will require complexity of O(R2).

G. L1 is an array so accessing element or checking size is constant time operation. L4 is doubly linked list which will need to traverse whole to check wether element exists or not. Hence operation cost O(S). we are doing this for each element of L1, hence O(P) * O(S) = O(P * S)

H. For each element of L1 (array) we are checking is it equal to any of the item in L4 (circular doubly linked list). So again accessing item from L1 and checking its size is O(1). Getting an item from L4 will cost O(S). Hence each L4.get(j) will cost O(j). So inner loop will cost as follows:

O(1) + O(2) + ... + O(S) = O(S2) [only for inner loop]

So for each element of L1 inner loop will be executed. Hence total worst cast complexity O(P) * O(S2) = O(P * S2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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