Match List I with List II

1. AA-I B-III C-IV D-II
2. BA-IV B-III C-II D-I
3. CA-I B-II C-IV D-III
4. DA-IV B-II C-III D-I

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. A-IV B-III C-II D-I

Explanation

Plain recursion for Fₙ takes Θ(φⁿ); memoization gives O(n); repeated squaring (integer addition and multiplication only) gives O(log n); the optimal bitonic tour DP takes O(n²).