Was working on a leetcode problem and received feedback that the following block of code is of O(n^3) time complexity. Can someone help explain to me how this is so? I count two loops which led me to believe this was O(n^2).
var longestPalindrome = function(s) {
let maxString = "";
let originalString = s;
let reversedString = s.split("").reverse().join("");
for (let i = 0; i < s.length; i++){
for (let j = i+1; j < s.length+1; j++){
if (i<j){
let iteratedSubstring = originalString.substring(i,j)
if (reversedString.includes(iteratedSubstring) && (iteratedSubstring === iteratedSubstring.split("").reverse().join("")) ){
iteratedSubstring.length > maxString.length ? maxString = iteratedSubstring: maxString = maxString
}
}
}
}
return maxString
}
The if block is executed O(𝑛²) times, but the body of that block is not O(1):
originalString.substring(i,j) may have O(𝑗−𝑖) time complexity (depending on implementation), so that would average to a time complexity of O(𝑛). See also: Is Javascript substring virtual?reversedString.includes(iteratedSubstring) has O(𝑛) time complexityiteratedSubstring.split("") has O(𝑛) time complexity.reverse() has O(𝑛) time complexity.join("") has O(𝑛) time complexitySo there are several reasons why that if block has a time complexity of O(n), giving an overall time complexity of O(𝑛³)