You have a large unsorted set of n records that you wish to

You have a (large) unsorted set of n records that you wish to store in a BST. The BST will be built by adding one record at a time. Will it be faster to build the BST if the records are first sorted so that they can be added to the BST in sorted order? Yes or no? Explain.

Solution

In case of n unsorted records, each elements require O(log n) time to search its position. So, overall time taken to build BST is O(n logn). But when we have sorted records, we can have 2 options:

So, sorting records will not be of any help (asymptotically). Even in worst case, they may take more time.

Hope it helps, do give your response.