Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

263
Views
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 answers
Answer question

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 Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
ยฉ 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!