Time Complexity of Brute Force Approach for finding Longest Increasing Subsequence (LIS)

To find the Longest Increasing Subsequence (LIS) of a sequence of length n, the brute force approach involves checking all possible subsequences of the given sequence. Here's how the time complexity is determined:

1. Generating all subsequences:
The brute force approach generates all possible subsequences of the given sequence. Since each element in the sequence can either be present or absent in a subsequence, there are 2^n possible subsequences.

2. Checking if each subsequence is increasing:
For each generated subsequence, the brute force approach checks if it is an increasing subsequence. This involves comparing each element in the subsequence with its previous element. The check takes O(n) time.

Therefore, the overall time complexity of the brute force approach is O(2^n * n). Here's a breakdown of the time complexity:

- Generating all subsequences: O(2^n)
- Checking if each subsequence is increasing: O(n)

Explanation:
The brute force approach generates all 2^n possible subsequences of the given sequence. For each subsequence, it then checks if it is an increasing subsequence by comparing each element with its previous element. Since there are n elements in the subsequence, this check takes O(n) time.

As a result, the time complexity of generating all subsequences is O(2^n), and for each subsequence, the check takes O(n) time. Therefore, the overall time complexity is O(2^n * n).

Example:
Consider a sequence of length 3: {1, 5, 2}

The brute force approach will generate the following subsequences:
- {1}
- {5}
- {2}
- {1, 5}
- {1, 2}
- {5, 2}
- {1, 5, 2}

For each subsequence, the approach checks if it is an increasing subsequence:
- {1} - increasing
- {5} - increasing
- {2} - not increasing
- {1, 5} - increasing
- {1, 2} - not increasing
- {5, 2} - not increasing
- {1, 5, 2} - not increasing

Therefore, the longest increasing subsequence is {1, 5}, and the brute force approach checks all possible subsequences to find it.

Conclusion:
The brute force approach for finding the Longest Increasing Subsequence (LIS) has a time complexity of O(2^n * n). This is because it generates all 2^n possible subsequences and checks if each subsequence is an increasing subsequence in O(n) time.