Register

NIELIT 2021 Dec Scientist A - Section B: 55

• edited by
416 views
0 votes
0 votes

If a hash table is implemented as a search tree, the expected time required to enter $\text{n}$ names and make $\text{m}$ searches is proportional to :

  1. $\text{(n+m)} \log_{2} \text{n}$
  2. $\text{(n+m)} \log_{2} \text{m}$
  3. $\text{mn} \log_{2} \text{n}$
  4. $\text{mn} \log_{2} \text{m}$
• edited by
User Avatar

1 Answer

0 votes
0 votes

(A)  (n+m) log2 n ….

 

 

 

If names are encountered in random order, the average length of a path in the tree will be proportional to log n, where n is the number of names....

Therefore each search follows one path from the root, the expected time needed to enter n names and make m inquiries is proportional to (n + m) log n ….

If n is greater than about 50, there is a clear advantage to the binary search tree over the linked list and probably over the linked self-organizing list….

 

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
soujanyareddy13 asked Jan 9, 2022
947 views
NIELIT 2021 Dec Scientist A - Section B: 43
Let the predicates $D(x,y)$ mean team $x$ defeated team $y$ and $P(x,y)$ mean team $x$ has played team $y$ ... $ \forall y \exists x (P(x,y) \rightarrow D(x,y))$ $\exists x \forall y (D(x,y) \rightarrow P(x,y))$
Let the predicates $D(x,y)$ mean “team $x$ defeated team $y$” and $P(x,y)$ mean “team $x$ has played team $y$”. The quantified formula for the statement that ther...
User Avatar
0 votes
0 votes
1 answer
2
soujanyareddy13 asked Jan 9, 2022
604 views
NIELIT 2021 Dec Scientist A - Section B: 44
The File Transfer Protocol is built on ______________. data centric architecture service-oriented architecture client server architecture connection-oriented architecture
The File Transfer Protocol is built on ______________.data centric architectureservice-oriented architectureclient server architectureconnection-oriented architecture
User Avatar
0 votes
0 votes
1 answer
3
soujanyareddy13 asked Jan 9, 2022
529 views
NIELIT 2021 Dec Scientist A - Section B: 45
More than one word is put in one cache block to: exploit the temporal locality of reference in a program exploit the spatial locality of reference in a program reduce the miss penalty none of the option
More than one word is put in one cache block to:exploit the temporal locality of reference in a programexploit the spatial locality of reference in a programreduce the mi...
User Avatar
0 votes
0 votes
1 answer
4
soujanyareddy13 asked Jan 9, 2022
446 views
NIELIT 2021 Dec Scientist A - Section B: 46
In $\text{DPSK}$ technique, the technique used to encode bits is : $\text{AMI}$ Differential code Unipolar $\text{RZ}$ format Manchester formate
In $\text{DPSK}$ technique, the technique used to encode bits is :$\text{AMI}$Differential codeUnipolar $\text{RZ}$ formatManchester formate
User Avatar
Link Copied!