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: Its average-case complexity for uniformly distributed data is O(n). - Matrix chain multiplication: A dynamic programming solution results in O(n3) complexity. - Huffman codes: This greedy algorithm exhibits O(n lg n) complexity, primarily due to sorting. - Dijkstra’s Algorithm: Implemented with an adjacency matrix, it runs in O(n2).