Match the following : \(\begin{array}{} & \textbf{List – I} & & \textbf{List –…
2014
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}\)
Codes :
- A.
a-iv, b-ii, c-i, d-iii
- B.
a-ii, b-iv, c-i, d-iii
- C.
a-iv, b-ii, c-iii, d-i
- D.
a-iii, b-ii, c-iv, d-i
Attempted by 86 students.
Show answer & explanation
Correct answer: C
Correct matching and brief justification:
Bucket sort → O(n).
Reason: Under the standard uniform-distribution assumptions, elements are placed into buckets and processed in linear time overall (one pass to distribute plus linear time to collect).
Matrix chain multiplication → O(n^3).
Reason: Dynamic programming solution uses three nested loops over chain indices, giving cubic time.
Huffman codes → O(n log n).
Reason: Building the Huffman tree with a min-heap (priority queue) requires about n extract/insert operations, yielding O(n log n).
All-pairs shortest paths → O(n^3 log n).
Reason: Running Dijkstra from each vertex using a binary heap on a dense graph results in O(n) runs each costing O(n^2 log n) in the dense case, leading to O(n^3 log n). (Note: an alternative algorithm, Floyd–Warshall, runs in O(n^3), but the intended matching uses the repeated-Dijkstra complexity.)
Final matched mapping:
Bucket sort → O(n)
Matrix chain multiplication → O(n^3)
Huffman codes → O(n log n)
All-pairs shortest paths → O(n^3 log n)