Register

NIELIT 2016 MAR Scientist C - Section C: 52

• retagged by
1,944 views
3 votes
3 votes

Consider the process of inserting an element into a $Max\ Heap$, where the  $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is

  1. $\Theta(\log _{2}n)$
  2. $\Theta(n\log _{2} \log_2 n)$
  3. $\Theta (n)$
  4. $\Theta(n\log _{2}n)$
• retagged by
User Avatar

1 Answer

1 votes
1 votes

Ans- Option B

first find the length of tree it will take O(log n) time 

and after applying binary search on path it will take  O(log(log n)) time  

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

Related questions

1 votes
1 votes
1 answer
1
admin asked Apr 2, 2020
712 views
NIELIT 2016 MAR Scientist C - Section C: 49
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is$\Theta (\lo...
User Avatar
2 votes
2 votes
2 answers
2
admin asked Apr 2, 2020
1,090 views
NIELIT 2016 MAR Scientist C - Section C: 30
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is $6$ $5$ $4$ $3$
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum...
User Avatar
2 votes
2 votes
2 answers
3
admin asked Apr 2, 2020
802 views
NIELIT 2016 MAR Scientist C - Section C: 31
A full binary tree with $n$ non-leaf nodes contains $\log_ 2 n$ nodes $n+1$ nodes $2n$ nodes $2n+1$ nodes
A full binary tree with $n$ non-leaf nodes contains$\log_ 2 n$ nodes$n+1$ nodes$2n$ nodes$2n+1$ nodes
User Avatar
Link Copied!