educative.io

What is the running time of Longest Common Substring with memoization

Courses
,
#1

Hi All,

int maxLength = Math.min(s1.length(), s2.length());
Integer[][][] dp = new Integer[s1.length()][s2.length()][maxLength];

My analysis is that since we have a 3d array the running time will be bounded by
O(mn(min(m,n)))
where m is s1 length and n is s2 length

Please do correct me if I am mistaken
Thanks :slight_smile:

#2

Yes, you’re correct. The runtime complexity would be O(nmmin(n,m)) rather than an exponential complexity like the basic LCS solution.

We used memoization which allows us to store data and only make a recursive call when dp[i][j][k] is null. This means that the recursive call is only made nmmin(n,m) times, which gives us our above time complexity.