Consider these two routines, the first builds a binary search tree, and the second uses that to sort an array A of n comparable elements. Here inorderTrav performs an inorder traversal of the tree T.

 buildBST(array A) { BST T 

for i=1 to n

T.insert(A[i])

return T }

BSTsort(array A) { BST T = buildBST(A)

T.inorderTrav() }

(a) What is the worst case time of BSTsort?

(b) What is the average case time of BSTsort?