ISRO-DEC2017-45

Question

Match the following and choose the correct answer in the order $A, B,C$

$\begin{array}{|ll|ll|} \hline \text{A.} & \text{Heap Construction} & \text{p.} & O(n\log n) \\\hline \text{B.} & \text{Hash Table construction with linear probing} & \text{q.} & O(n^2)  \\\hline \text{C.} & \text{AVL Tree Construction} & \text{r. }& O(n) \\\hline  \end{array}$

(Bounds given may or may not be asymptotically tight)

• A.  $a-q,b- r, c-p$
• B.  $a-p, b-q, c-r$
• C.  $a-q, b-p, c-r$
• D.  $a-r, b-q, c-p$

Comments

option D

Answer 1

Heap Construction- O(n)

Hash table construction with linear probing- O($n^{2}$)

AVL Tree construction- O(nlogn)

option D

Answer 2

Build Heap — O(n)

---

AVL tree construction — O(nlogn).

For a node, we'd take O(logn) time to find it's correct place, and to fix the height if needed. For n such nodes, O(nlogn)

---

Hash Table with LP — $O(n^2)$

In the worst case for an element, we'd have to traverse the entire list to put the element in an empty slot. So, O(n).

For n such elements,  $O(n^2)$

---

Option D