Question

Match List I with List II;

LIST I	LIST II
(A) Bucket sort	(I) O(n²)
(B) Matrix chain multiplication	(II) O(n³)
(C) Huffman codes	(III) O(n log n)
(D) Dijkstra’s Algorithm	(IV) O(n)

Choose the correct answer from the options given below:

• (A) - (II), (B) - (III), (C) - (I), (D) - (IV)
• (A) - (II), (B) - (III), (C) - (IV), (D) - (I)
• (A) - (IV), (B) - (III), (C) - (I), (D) - (II)
• (A) - (III), (B) - (II), (C) - (IV), (D) - (I)

Hint:

Familiarize yourself with the complexities of sorting, searching, and graph algorithms for such questions.

Answer 1

The Correct Option is D

- Bucket sort: Average-case complexity is O(n) for uniformly distributed data. - Matrix chain multiplication: Dynamic programming solution with O(n3) complexity. - Huffman codes: Greedy algorithm with O(n lg n) complexity due to sorting. - Dijkstra’s Algorithm: Runs in O(n2) using an adjacency matrix.