Find time and space complexity of the following code Public Class MinimumCutsPli
ID: 2247483 • Letter: F
Question
Find time and space complexity of the following code
Public Class MinimumCutsPlindromes {
public int minCuts(Spring input) {
//assumption:input is not null//
char[] array = input.toCharArray();
int len = array.length;
if (len == 0) {
return 0;
}
//ifP[i][j] indicates if the substring (i-1, j-1) is palindrome//
boolean[][] isP = new boolean[len + 1][len +1];
//minCuts[i] indicates the min cuts for substring (0, i-1)//
int[] minCuts = new int[len + 1];
for (int end = 1; end <= leng; end++) {
minCuts[end] = end;
for (int start = end; start >= 1; start--) {
if (array[Start - 1] == array[end - 1]) {
isP[start][end] = end - start < 2 || isP[Start + 1][end - 1];
}
//use isP[start][end] to calculate minCuts[end]//
if (isP[start][end]) {
minCuts[end] = Math.min(minCuts[end], 1 +minCuts[Start - 1]);
}
}
}
return minCuts[len] - 1;
}
}
Explanation / Answer
For time complexity :
Initially we only have constant time operations and no loops until the 13th line so the complexity up to 13th line is O(k) where k is a positive constant.
But from 13th line we have indented for loops
The outer loop runs from 1 to leng so we have this loop running for ~leng iterations
The inner loop runs from end to 1. The max value of end is leng so worst case we have ~leng iterations in this loop as well
Thus the two loops combined have a complexity of O (leng * leng) which is up to line 15g.
From line 16 to 20 we again have constant operations equal to O(k’) where k’ is a positive constant.
The O(k) and O(k’) can be ignored when compared to the O(leng * leng) asymptotically and hence the time complexity can be evaluated as O(leng * leng)
For Space Complexity
Line 4 has space complexity of O(len+1) = ~O(len)
Line 10 has space complexity of O((len+1) * (len+1)) = ~O(len*len)
Line 12 has space complexity of O(len+1) = ~O(len)
Thud the overall space complexity is O(len) + O(len*len) + O(len) = ~ O(len*len) because O(len) can be ignored asymptotically when compared to O(len*len).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.