The Gateway to Computer Science Excellence
+1 vote
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
in Algorithms by Active (4.4k points) | 168 views
If there was any method which was more efficient (say O(n)), then we could build the tree in O(n) and then do an inorder traversal in O(n), thus sorting the array in O(n), which is a contradiction. Hence, any method to build a BST will take at least $\Omega(n \log n)$

Please log in or register to answer this question.

Related questions

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,378 answers
105,316 users