+1 vote
84 views
Could a binary search tree be built using o(n lg n) comparisons in the comparison
model? Explain why or why not.
| 84 views
+1
It should be O(n^2)
+1
abhishekmehta4u can you explain How it should be $O(n^2)$

+1 vote

NO, or else we could sort in o(n lg n) time by building a BST in o(n lg n)
time and then doing an in-order tree walk in O(n) time.

by Loyal (5.7k points)
selected

In case of skewed BST (worst case) :  O(n2)

Inserting first element ; 0 comparison

Inserting second element : 1 comparison

Inserting nth element : n-1 comparisons

Total : O(n2) comparisons

In case of Balanced BST : O(nlogn)

by Active (1.6k points)

+1 vote