What is the time complexity of the following dynamic programming implementation of the longest common subsequence proble

[answerhappygod]

advertisement


var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
}
});
#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[0] = 0;
for(i = 0; i <= len2; i++)
arr[0] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[j] = 1 + arr[j - 1];
else
arr[j] = max_num(arr[j], arr[j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = " abcedfg", str2[] = "bcdfh";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}
a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)