0

I found some very helpful solutions to writing a Javascript function that recursively checks whether a string is a palindrome here. I would like to know what the time and space complexity of the following solution would be. Can you explain how each line contributes to big O?

function isPalindrome(string) {
    if (string.length < 2) return true;
    if (string[0] === string[string.length - 1]) {
        return isPalindrome(string.slice(1, string.length - 1))
        }
    return false;
}
Hilary L
  • 26
  • 2
  • 1
    Depends on how efficiently `string.slice` is implemented. It might be anywhere between `O(n)` and `O(n²)`. – Bergi Apr 29 '20 at 20:06
  • 4
    No, we can't explain big O in detail. Can you show us your attempt at deriving the big O of the function, so that we can fill in the gaps? – Bergi Apr 29 '20 at 20:07
  • @Bergi is the variance between `O(n)` and `O(n²)` based on the JS engine's implementation of `slice`? – Honinbo Shusaku Apr 29 '20 at 20:12
  • @Abdul Yes. (Also, it's important to state that it is the worst case complexity, not the average case complexity) – Bergi Apr 29 '20 at 20:14

2 Answers2

2

At first it would seem that your function is O(n), because you call it recursively n/2 times. However, in each call you also use string.slice, which has a complexity of O(n). Because of that, your function is actually O(n^2)

Alejandro De Cicco
  • 1,216
  • 3
  • 17
  • 2
    "*which has a complexity of O(n)*" - how do you know? – Bergi Apr 29 '20 at 20:08
  • I completely forgot to take `slice` into account! However, Bergi's comment still stands : how do you know it's O(n)? – Pac0 Apr 29 '20 at 20:11
  • Well, I quickly checked [this](https://stackoverflow.com/a/22615787/12950351) and since it was accepted I thought it was correct. However you are right, it could be worse depending on the implementation. – Alejandro De Cicco Apr 29 '20 at 20:29
0

You recursively call the function n/2 times, where n is the length of the string, since you remove first and last entry of the string at each iteration.

Therefore, the complexity would be O(n/2) = O(n), and you have at most 3 operations at each function call. That would multiply all this by a constant, which does not change the complexity.

EDIT: as noted in comments and another answer, one of these operations is string.slice. You need to check for the complexity of this, because it will multiply as well and can change overall complexity. If slice is O(1) constant, then overall you'll have O(n). If slice is O(n), then overall that would be O(n^2).

For space complexity, you create a lot of arrays. I'll let you the details, but I'm tempted to say it's O(n^2) at first sight.

Sketch of calculations : first array is size n, then n-2, n-4, sum that all up with some math summation formulas.

hint : n + (n-1) + (n-2) + ... is n * (n + 1) / 2 which is O(n^2), that should give enough "feel" that this is O(n^2) too.

Pac0
  • 21,465
  • 8
  • 65
  • 74
  • "*you create a lot of arrays*" - I was assuming that the `string` variable contains a string, not an array :-) For arrays, we know that `slice` is `O(n)` (both space and time avg complexity). Btw, your space complexity calculation doesn't seem to take into account garbage collection. – Bergi Apr 29 '20 at 20:16