The Gateway to Computer Science Excellence
+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 by (291 points) | 84 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.

by Loyal (5.7k points)
selected by
0 votes

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)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
104,978 users