My thought process on this is that this algorithm is incorrect. To create a binary tree from an unsorted array of size n of integers, one would need to first sort the array. We know that any comparison-based sorting algorithm has a lower bound runtime of omega(nlog(n)), as in we can't get better than that.
Once the array is sorted, we need a way to create the BST properly. (Looking at the keys/nodes in-order would have to be in an increasing/sorted manner) we look at the middle element of the array and make it the root of our tree. We then do this recursively on the left half of the array, construct the left subtree, and make it the left child of the root. We also do this recursively on the right half of the array, construct the right subtree, and make it the right child of the root. The runtime of this will be O(n) due to the recurrence relation: T(n) = 2T(n/2) + c. This is happening after our sorting above so the total runtime would be O(nlog(n) + n) which is just O(nlog(n)). This shows that there is no way that we can get better than this.
Is there anything I can add or is this sufficient? Anybody have other suggestions/thoughts? Thanks.
You've assumed that to create a binary tree you need to first sort the integers as a first step. Since that's an unjustified assumption, your proof is invalid.
To correctly prove the result, you need to assume that you can create the BST in nloglogn comparisons, and from that prove a contradiction. The contradiction is immediate, since from a BST you can get a sorted list of integers in linear time (from an inorder traversal of the tree), so you would have a nloglogn comparison sort.
This proof is probably what the person setting the question intended, but I think the premise of the question is false. As you presented it, the question doesn't specify that the only operations on the given integers are comparisons, so it's possible that Professor X's algorithm makes the binary search tree with operations that aren't comparisons. Then there wouldn't be a contradiction because it could be used to sort integers but not be a comparison sort. For example, fusion trees can be used to sort n integers in less than O(n log n) arithmetic operations (see https://www.sciencedirect.com/science/article/pii/0022000093900404).