CODEWITHSUNDEEP
algorithmtime-complexitybig-opalindromespace-complexity
SamuelP
SamuelP

Reputation: 195

Time and Space Complexity of this Palindrome Algorithm?

Can someone tell me the time and space complexity for this algorithm? Basically the function takes in a string and the function must return true if it's a palindrome (same backwards as it is forwards) or false if it is not.

I am thinking it is O(n) for both but please correct me if I am wrong.

function isPalindrome(string) {
    var reversing = string.split("").reverse().join("")
    return string === reversing
}

Upvotes: 0

Views: 1515

Answers (1)

chqrlie
chqrlie

Reputation: 145317

Your function has a time and space complexity of O(string.length) because it constructs an array of characters and then a new string with the characters in reverse order, with the same length as the original string. Comparing these strings has the same time complexity.

Note however that this works for single words but not for complete phrases: a phrase that can be read in both directions with the same letters, but not necessarily the same spacing is also a palindrome.

Here is an alternative version:

function isPalindrome(string) {
    string = string.replace(/ /g, "");
    var reverse = string.split("").reverse().join("");
    return string === reverse;
}

This function has the same time and space complexity of O(string.length).

Upvotes: 2

Related Questions