# Sorting

1 vote
359 views
Could a binary search tree be built using o(n lg n) comparisons in the comparison
model? Explain why or why not.
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.

selected
1 vote

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)

## Related questions

1
687 views
2
264 views
i mark the option D) but answer is A)
3
444 views
When the recurrence relation for both are same , why they both getting different result? Q1. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort? ANSWER: recurrence ... doubt is If for first case it is N(log3/2N) then for second case also it should be N(log4/3N) BUT its not. WHY?