Home »
MCQs »
Algorithms MCQs
Which of the following is the time complexity of the naive recursive implementation of the LCS problem?
33. Which of the following is the time complexity of the naive recursive implementation of the LCS problem?
- O(m * n)
- O(m^2)
- O(2^(m+n))
- O(m + n)
Answer
The correct answer is: C) O(2^(m+n))
Explanation
The naive recursive implementation has an exponential time complexity because it explores all possible subsequences.