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(๐ยณ)