CODEWITHSUNDEEP
javascripttime-complexitybig-ospace-complexity
Moe
Moe

Reputation: 73

What is the space complexity of this longest palindrome function?

function longestPalindromicSubstring(str) {
    let longest = '';
    for ( let i = 0; i < str.length; i++) {
         let word1 = palindromeFinder(str, i, i );
         let word2 = palindromeFinder(str, i, i+1);
         longest = [ word1, word2, longest ].reduce( (long, word) => long.length > word.length ? long : word)
    }
    return longest;
}

function palindromeFinder(str, left, right) {
    while ( left >= 0 && right < str.length && str[left] === str[right] ) {
        left--;
        right++;
    }
    return str.slice(left + 1, right)
}

I am pretty sure the Time complexity is O(n^2) because of the main for loop times the loop in the helper function. In the for loop, I am using the reduce function but it only does 2-3 operations for every element in the input string...am I wrong to assume O(n^2)?

My main question is: is the space complexity of this function O(1)?

At most I am storing 3 variables longest, word1, word2 so that would make it constant right?

Upvotes: 0

Views: 94

Answers (2)

Mbiplang Ardel
Mbiplang Ardel

Reputation: 700

What causes space complexity?

  1. Variable
  2. Data Structures
  3. Function Call
  4. Allocations

these things take up space, and when it comes to time and space complexity the worst-case scenario is considered and constant time (O(1)) is ignored.

However, your function has variables assigned, new data structure, function call which makes the space complexity to be O(n), also, each item of the array consumes additional space.

Upvotes: 1

peter
peter

Reputation: 593

The space complexity for this function is O(n), since you store constant number of data structures, each depending on n: str, word1, word2, longest. O(1) actually means constant, which is definitely not the case

Upvotes: 0

Related Questions