edited by
5,016 views
14 votes
14 votes
Match the pairs in the following questions:$$\begin{array}{|ll|ll|} \hline  (a) & \text{A heap construction} & (p) & \ \Omega(n\log_{10}n)  \\\hline (b) & \text{Constructing Hashtable with linear probing} & (q) & \ O(n) \\\hline (c) & \text{AVL tree construction} &  (r) & \ O(n^{2})  \\\hline (d) & \text{Digital trie construction} & (s) & \ O(n\log_{2}n) \\\hline \end{array}$$
edited by

3 Answers

Best answer
22 votes
22 votes

$(A)$ A heap Construction(Build  heap) : -

Build-Heap (A)

  1. heap-size$[A]$ $\leftarrow$ length$[A]$

  2. for $ i \leftarrow$ $\left \lfloor l\text{ength}[A] / 2  \right \rfloor$ downto $1$

  3.        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$

selected by
1 votes
1 votes
  1. Constructing a heap will require you to use heap-ify at all elements, $n*O(1) = O(n)$
  2. If all elements of a hash table get mapped to the same slot for the $n_{th}$ element you'd have to traverse $n-1$ elements already in the slot $ n*(n-1)= O(n^2)$  
  3. AVL Tree will always take $O(n*log(n))$
  4. A Trie for string which consists of characters in $[0,9]$ will take $\Omega(n*log_{10}(n))$ and at worst $O(n^2)$ (if all strings comprise of a single character eg: 0, 00, 0000, 000000, 00000)

    Answer: a-q, c-s, b-r, d-p  
0 votes
0 votes

Heap construction -          O(n)    ( No max or min heapification only Heap construction)

Constructing hash table -  O(n)

AVL tree construction    - O(n log2 n)

Digital trie construction -  O(no of string * avg. length of string )

Related questions

21 votes
21 votes
2 answers
1
makhdoom ghaya asked Nov 19, 2016
3,860 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Groups} & (p) & \text{Associativity} \\\hline (b) & \text{Semigroups} & (q) & \text...
29 votes
29 votes
3 answers
2
makhdoom ghaya asked Nov 19, 2016
14,268 views
Match the pairs in the following questions:$$\begin{array}{ll|ll} (a) & \text{Lexical analysis} & (p) & \text{DAG's} \\\hline (b) & \text{Code optimization} & (q) & \tex...
11 votes
11 votes
1 answer
3
makhdoom ghaya asked Nov 19, 2016
5,833 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Strassen's matrix multiplication algorithm} & (p) & \text{Greedy method} \\\hline (...
4 votes
4 votes
1 answer
4
makhdoom ghaya asked Nov 19, 2016
2,261 views
Match the pairs in the following questions:(a) Small talk(p) Logic programming(b) LISP(q) Data flow programming(c) Prolog(r) Functional programming(d) VAL(s) Object-orien...