0
$\begingroup$

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 ? "

Trace :

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)

$\endgroup$
  • $\begingroup$ How will you move to next character for both strings if there is a match? The inner loop will be reset when you move for next character in outer loop. Once reset what if there is a match for the next character before the previous match. Your approach does not solve the problem, let alone the complexity. $\endgroup$ – Navjot Waraich Mar 14 at 23:00
  • 1
    $\begingroup$ Try two strings with duplicate characters and you will see your approach failing. $\endgroup$ – Navjot Waraich Mar 14 at 23:03
  • $\begingroup$ "I compute all the possible subsequence." That sounds like exponential operations. Anyway, the description of your algorithm is not clear enough. Can you add a link to your code such as a page on replt.it? As @NavjotWaraich suggested, have you tried two strings such as "ababababa" and "acacacaca", whose longest subsequence should be "aaaaa"? $\endgroup$ – Apass.Jack Mar 15 at 0:21
  • $\begingroup$ @NavjotWaraichI tried with duplicate strings also.. $\endgroup$ – Shahriar Mim Mar 16 at 15:37
  • $\begingroup$ @Apass.Jack here's my code [link]ideone.com/SDiv0q (updated). I printout the the maximum number of longest sub-sequence. As it is just a Time Complexity checking, I tried to make the code simple with basic operations. I hope you will understand the code. $\endgroup$ – Shahriar Mim Mar 16 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.