Consider the following sorting algorithm I Insert the given

Consider the following sorting algorithm: I. Insert the given input A[1], A[2], .... A[n] into a binary search tree T in the given order, starting from an empty tree; II. Do an in order traversal of T to output the elements in non-decreasing order. (a) What is the worst case time for the algorithm? (b) What is the best case time for the algorithm?

Solution

(a)

For inserting 1 elements into binary tree, it will takes O(h) time, where h is the height of the tree.

For inserting n elements into binary tree, in worst case it will take O(n^2) time. The worst case is when we insert n sorted numbers in increasing order. In this case total time for insertion will be O(1+ 2 + 3 + .....+ n ) = O(n^2)

And inorder traversal will take O(n) time in worst case.

So, worst case time for overall algorithm is O(n^2).

(b)

In best case, inserting n elements into binary search tree will take O(nlogn) time, and inorder traversal of the tree will take O(n) time. So best case time for overall algorithm is O(nlogn).