Match List-I (Dynamic algorithm) with List-II (Average case running time) and select the correct answer using the codes given below the lists:
List-I (Dynamic algorithm)
A. Matrix chain multiplication
B. Travelling salesman problem
C. 0/1 knapsack
D. Fibonacci series
List-II (Average case running time)
1. O(mn)
2. O(n3)
3. O(nn)
4. O(n)
Codes:
A B C D
(a) 1 3 2 4
(b) 1 3 3 2
(c) 2 3 3 2
(d) 2 3 1 4