What Is The Time Complexity Of The Following Dynamic #2074

What is the time complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is "m" and the length of the other string is "n"?</p> <pre><code class="language-c"> #include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }</code></pre>

This multiple choice question (MCQ) is related to the book/course gs gs122 Data Communication and Computer Network. It can also be found in gs gs122 Dynamic Programming - Longest Common Subsequence - Quiz No.1.

 #include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }