$(A)$ A heap Construction(Build heap) : -
Build-Heap (A)
-
heap-size$[A]$ $\leftarrow$ length$[A]$
-
for $ i \leftarrow$ $\left \lfloor l\text{ength}[A] / 2 \right \rfloor$ downto $1$
-
do Heapify $( A, i )$
Note that $A[ ( \left \lfloor n/2 \right \rfloor + 1) \ldots n]$ are all leaves so they are length $1$ heaps.
Trivial Analysis: Each call to Heapify requires $\log(n)$ time, we make $n$ such calls $\implies O(n \log n).$
Tighter Bound: Each call to Max-Heapify requires time $O(h)$ where $h$ is the height of node $i.$ Therefore running time is $$\sum_{h=0}^{\log n}\dfrac{h}{2^{h}+1}\times O(h) = O\left(n \ \sum_{h=0}^{\log n}\dfrac{h}{2^{h}} \right)$$where $2^{h} + 1 = $ Number of nodes at height $h$ and $O(h) = $ Running time for each node.$$= O\left(n \ \sum_{h=0}^{\infty}\dfrac{h}{2^{h}} \right) = O(n)$$ Note: $\sum_{h=0}^{\infty}\dfrac{h}{2^{h}} = 2$
Reference:
$(B)$ Constructing Hash table with linear probing for $n$ elements has time complexity $\implies O(n^{2})$ in the worst case. This happens when all the $n$ elements are hashed to the same location and this means the number of probes will go like $0, 1, 2, 3, \ldots n-1$ for the $n$ elements giving the total number of probes $\frac{n.(n-1)}{2}$ which is $O(n^2).$
$(C)$ AVL Tree construction : -
- AVL trees are height-balanced binary search trees.
- Balance factor of a node : height(left subtree) $-$ height(right subtree).
- An AVL tree has balance factor calculated at every node, for every node, heights of left and right subtree can differ by no more than $1.$
- Constructing an AVL tree, to create a tree we have to insert $n$ elements in it. To insert the element in a balanced tree we need $\log(n).$ Therefore we can do this with $O(n\log(n))$ time complexity.
- We can traverse an AVL tree in $O(n)$ time and the inorder traversal gives the sorted list of $n$ elements. Since, sorting of $n$ elements takes minimum $\Omega(n \log n)$ time this also implies that creation of AVL tree is $\Omega (n \log n).$
- From above two points we get the time complexity of AVL tree creation as $\Theta(n \log n)$
Reference:
$(D)$ Digital trie construction of $n$ keys with maximum length $m$ requires $O(n \times m)$ time. Among the options $m$ is not specified and assuming $m$ is constant (small length keys), the time complexity will be $O(n)$ which is also $O(n \log n).$ So, $(s)$ gets mapped to $(D)$ and $(p)$ to $(C)$ though both $(p)$ and $(s)$ are possible for $(C).$
Correct Answer:
$A - q, B -r, C - p, D - s$
