I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am applying my brute force technique it's taking O(mn) (from my personal observation). I would like to request you please read my approach clearly and visualize in mind and ask question for further clarification if needed. My Approach is following:- Say we have two strings s1 = "ECDGI" , s2 = "ABCDEFGHIJ". Now what I am doing is I chose either one of the given strings. For say, s1. for i = 1 to n (n is the last index of s1), I am taking each value and comparing with the s2 in such a way that for a single character of s1 I am checking with all the characters of s2. Mathematically, ith value is checking through all jth value up to m (m is the last index of s2). Here, if I find any common character I just move to next character from both strings. Then just compute subsequence. I compute all the possible subsequence for each characters from s1 by running n loops. Finally, I compute the largest value. From my understanding it's taking O(mn) time complexity overall. So My Question is, " Is my Time Complexity Calculation right ? "
i = 1, value = E, lcs = 3 [EGI]
i = 2, value = C, lcs = 4 [CDGI]
i = 3, value = D, lcs = 3 [DGI]
i = 4, value = G, lcs = 2 [GI]
i = 5, value = I, lcs = 1 [I]
Answer is = 4 (maximum lcs)