1

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
}
ks1322
  • 33,961
  • 14
  • 109
  • 164
Divine Ogbuefi
  • 13
  • 2

1 Answers1

3

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 complexity
  • iteratedSubstring.split("") has O() time complexity
  • .reverse() has O() time complexity
  • .join("") has O() time complexity

So there are several reasons why that if block has a time complexity of O(n), giving an overall time complexity of O(³)

trincot
  • 317,000
  • 35
  • 244
  • 286
  • Be also aware in this answer, if `n` is the length of `s` at first, it is not used this way in the whole answer. If we have a function of complexity O(n) in a loop of complexity O(m), the result will be O(nm) which is not equivalent to O(²). – T.Trassoudaine Sep 28 '21 at 09:08
  • @T.Trassoudaine, there is only one input size to the algorithm: the size of `s`. The fact that `iteratedSubstring` has its own size (i.e. −) is covered in the first bullet point: it averages to be also O(), which is why the three last bullet points can also mention O(). So I reassert: the in O() **always** refers to the length of `s` in this answer. – trincot Sep 28 '21 at 09:20
  • Yes but considering that O(n-m), with m < n averages to be O(n) is pessimistic, by the same reasoning, you could say O(n!) averages to be O(n^n). – T.Trassoudaine Sep 28 '21 at 09:41
  • @T.Trassoudaine, the total sum of all the `j-i` sizes that are calculated is given by the formula `1(n-1)+2(n-2)+...+(n-1)1`, which is `n(n+1)n/2-n(n+1)(2n+1)/6` which is O(n³). So this means the average time complexity for the single execution of `substring(j-i)` is O(n). – trincot Sep 28 '21 at 21:18