In order to find out the complexity of brute force approach, we need to first know the number of possible different subsequences of a string with length n, i.e., find the number of subsequences with lengths ranging from 1,2,..n-1. Recall from theory of permutation and combination that number of combinations with 1 element are ⁿC₁. Number of combinations with 2 elements are ⁿC₂ and so forth and so on. We know that ⁿC₀ + ⁿC₁ + ⁿC₂ + … ⁿC_n = 2ⁿ. So a string of length n has 2ⁿ-1 different possible subsequences since we do not consider the subsequence with length 0. This implies that the time complexity of the brute force approach will be O(n * 2ⁿ). Note that it takes O(n) time to check if a subsequence is common to both the strings. This time complexity can be improved using dynamic programming.