Part A : What is the average case time complexity for linear search on a sorted array? Explain (and/or draw a diagram).
Part B: Assuming that each new element/node must be added starting from the head, what is the average case time complexity to add n values to a linked list that that is initially empty and that will have its values sorted from smallest to largest. Explain (and/or draw a diagram).
Part C: What is the best case time complexity to delete a value from a full BST? Explain (and/or draw a diagram).
Part D : An O(nlogn) algorithm (e.g. mergesort) will always run faster than an O(n2 ) algorithm (e.g. selection sort) for all values of n. True or False? Explain.
Part E : An implementation of quicksort has its worst case of O(n2 ) for an inverse sorted array (e.g. from largest to smallest). What case will it be for an already sorted array (e.g. from smallest to largest)? Explain.