CODEWITHSUNDEEP
javascriptrecursiontime-complexitybig-opalindrome
Hilary L
Hilary L

Reputation: 26

What is big O of this javascript recursion solution to check whether a string is a palindrome?

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;
}

Upvotes: 0

Views: 207

Answers (2)

Pac0
Pac0

Reputation: 23174

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.

Upvotes: 0

Alejandro De Cicco
Alejandro De Cicco

Reputation: 1236

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)

Upvotes: 2

Related Questions