Question

What is the average case time complexity of tree sort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(log n)

This question was posed to me by my school principal while I was bunking the class.

I'd like to ask this question from Sorting topic in division Sorting of Data Structures & Algorithms II

Answer 1

Right answer is (b) O(n log n)

Best explanation: As on an average every element takes log n time for insertion in a binary search tree so for n elements O(n log n) time will be required on an average.