b. (5%) The best-case time complexity of insertion sort is θ(n logn).

6. (15%) Consider an n-node sorted singly linked list L, where the first node (ie., the head) stores the smallest data, the last node (i.e., the tail) stores the largest data, and thenode stores the smallest data. Given the address of L's head and a key, is it possible to search for the key in L in O(logn) time? Please explain your answer.