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

2 Answers

1 vote
Best answer

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 by
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

2 votes
1 answer
687 views asked Mar 19, 2018 in Algorithms pankaj_vir 687 views
0 votes
1 answer
2 votes
3 answers
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?
asked Jul 30, 2018 in Algorithms Rishav Kumar Singh 444 views
0 votes
1 answer
You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate? 1)QuickSort 2)MergeSort 3)HeapSort 4)Selection Sort Explain? How
asked Jul 8, 2018 in Algorithms pradeepchaudhary 673 views