Can anyone explain to me why the average runtime complexity of the program here – https://www.geeksforgeeks.org/tree-sort/ – is nlogn and not n^2logn? Similarly, why is the worst case time complexity n^2 and n^3?
The explanations for both the average and worst case runtime seem to only consider inserting the elements from the array into the tree. The runtime of doing an inorder tree traversal is O(n), so shouldn’t the runtimes in the link be multiplied by n?
Is it because the elements are simply being printed out and not added to a new array?