I want to verify my assumptions about Time and Space complexity of two different implementations of valid palindrome functions in JavaScript.
In the first implementation we are using a helper function and just pass pointers
const isPalindrome = str => {
return isPalindromeHelper(str, 0, str.length - 1);
}
const isPalindromeHelper = (str, start, end) => {
if (end - start < 1) return true;
return str[start] === str[end] && isPalindromeHelper(str, start + 1, end - 1)
}
In this case I am assuming that the time complexity is O(N) and the space complexity is O(N) as well.
However, let's say that instead of passing pointers we are slicing the string each time. And let's say that slice is O(n) operation.
const isPalindrome = str => {
if (str.length <= 1) return true;
if (str[0] !== str[str.length - 1]) return false;
return isPalindrome(str.slice(1, str.length - 1));
}
Would this push both Time and Space complexity to O(N^2) if slice was O(N) operation? Time because of time complexity of slice and Space would increase since we are constantly creating new strings?
Would this push both Time and Space complexity to O(N^2) if slice was O(N) operation? Time because of time complexity of
slice...
Yes, if we assume slice has a time complexity of O(𝑛), then we have O(𝑛−1 + 𝑛−2 + 𝑛−3 + ... + 1) which is O(𝑛²)
...and Space would increase since we are constantly creating new strings?
Again, if we assume slice allocates new memory for the slice, then we have (with the same formula) a space usage of O(𝑛²)
As strings are immutable, a JavaScript engine may benefit from memory that already has the string, and not really allocate new memory for slices. This is called string interning. This could bring both time and space complexity back to O(𝑛). However, since there is no requirement in the EcmaScript language specification to actually do this, we have no guarantee.
Both of them are recursive operations and run through the whole length of the string (n) n/2 times since they start at 0 and at n - 1 and they run until they meet at n/2.
In the O notation, this would mean both are O(n) since you can ignore the constant 2.