edited by
7,509 views

7 Answers

Best answer
5 votes
5 votes
option 3

Any decision tree that sorts n elements has height Omega(n lg n).

 

Proof:
A binary tree of height h has <= 2^h leaves.
At least n! leaves are required for sorting.
Thus n! <= 2^h.
    h >= lg(n!) = sum_{i=2}^n lg(i) > sum_{i=n/2}^n lg(i) > sum_{i=n/2}^n lg(n/2)
      >  (n/2) lg(n/2) = Omega(n lg n).
selected by
0 votes
0 votes
Option A) Best case scenario is to use a balanced binary tree. And the height of a balanced binary tree of n elements is logn.
Answer:

Related questions

0 votes
0 votes
5 answers
1
go_editor asked Mar 24, 2020
3,451 views
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5 $ is...
0 votes
0 votes
4 answers
2
go_editor asked Mar 24, 2020
2,096 views
Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm
0 votes
0 votes
6 answers
3
go_editor asked Mar 24, 2020
1,502 views
Match the following with respect to algorithm paradigms :$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{a.} & \text{Merge sort} & \text{i.} & \te...
0 votes
0 votes
4 answers
4
go_editor asked Jan 31, 2017
2,283 views
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic-set operations take _____ time in the worst case.$O(1...