SU is a singly linked list with a head and a tail pointer to the first and last element. Elements (keys) are inserted at the head of the list. Elements are kept unordered. (SU stands for Singly-linked list Unordered.)

DO is a doubly linked list with a head and a tail pointer to the first and last element. Elements (keys) are inserted starting from the head of the list, but the list is ordered (sorted) with the head pointer pointing at any time to the smallest and the tail pointer to the largest element. (DO stands for Doubly-linked list Ordered/Sorted.)

Before the next operation as described below, the list SU or DO contains already n elements. Describe the running time of the corresponding operation. We use n to indicate an operation that is of linear time, we use 1 to indicate a constant time operation and so on. In asymptotic notation this would have been Theta(n) or Theta(1) respectively based on the writing of Document 4.

(a) Find the MAX of SU [ Select ] ["n", "lgn", "1"]

(b) Delete the MAX of DO [ Select ] ["n", "lgn", "1"]

(c) Delete a spefic element of SU pointed by a given pointer/reference x [ Select ] ["1", "n", "lgn"]

(d) Insert an element into DO [ Select ] ["lgn", "1", "n"]

(e) Search for a specific key in DO [ Select ] ["n", "1", "lgn"]

(f) Find and Delete the MAX of DO [ Select ] ["n", "lgn", "1"]