Question

In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?

(a) O(n)

(b) O(n^2)

(c) O(n!)

(d) O(2^n)

This question was posed to me in semester exam.

My question comes from Longest Increasing Subsequence in division Dynamic Programming of Data Structures & Algorithms II

Answer 1

The correct option is (d) O(2^n)

For explanation: The time required to find all the subsequences of a given sequence is 2^n, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2^n).