Question

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

(a) O(n)

(b) O(n^2)

(c) O(n^3)

(d) O(2^n)

This question was addressed to me in an interview for internship.

My question is based upon Longest Common Subsequence topic in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct answer is (d) O(2^n)

Easiest explanation - The time complexity of the brute force algorithm used to find the longest common subsequence is O(2^n).