The Gateway to Computer Science Excellence
+1 vote
85 views
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 (1.9k points) | 85 views
+3
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,647 questions
56,492 answers
195,439 comments
100,707 users