Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

268
Vistas
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 Respuestas
Responde la pregunta

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 Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda