UGC NET CSE | December 2014 | Part 3 | Question: 32

Question

Match the following $:$

$\begin{array}{}  & \textbf{List – I} &  & \textbf{List – II} \\ \text{a.} & \text{Bucket sort} & \text{i.} & O(n^3\lg n)  \\ \text{b.} & \text{Matrix chain multiplication} & \text{ii.} & O(n^3) \\  \text{c.} & \text{Huffman codes} & \text{iii.} & O(n\lg n) \\ \text{d.} & \text{All pairs shortest paths} & \text{iv.} & O(n) \\  \end{array}$

$\textbf{Codes :}$

• A. $\text{a-iv, b-ii, c-i, d-iii}$
• B. $\text{a-ii, b-iv, c-i, d-iii}$
• C. $\text{a-iv, b-ii, c-iii, d-i}$
• D. $\text{a-iii, b-ii, c-iv, d-i}$

Answer 1

Bucket sort  = O(n)

Matrix chain multiplication = O(n³)

Huffman codes =O(n logn)

All pairs shortest paths = O(n³logn)

Ans is (C).