Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

264
Visualizações
Is this function O(n^3)?

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
}

about 4 years ago · Juan Pablo Isaza
1 Respostas
Responde à pergunta

0

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(𝑛³)

about 4 years ago · Juan Pablo Isaza Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda