CODEWITHSUNDEEP
algorithmrecursiontime-complexity
sheldon cooper
sheldon cooper

Reputation: 473

Time compexity of palindrome recursive algorithm

I have written this recursive function to find the palindrome.

def palindrome(string):
    print("palindrome called with:"+string)
    if(len(string)<=3):
        return string[0]==string[-1]
    else:
        res=palindrome(string[1:-1])
        print("palindrome returned:"+str(res))
        return res

I have yo find the time complexity of this algorithm of it now. My questions is my base case right? which is len<=3? I'm unable to relate this to classic examples of fibonacci and factorial algorithm which are everywhere on internet.

Upvotes: 3

Views: 3309

Answers (1)

harmands
harmands

Reputation: 1112

Yes, the fact is that only your base case is correct.

So what you should be doing here is, check if the first and last character are same, then check if the remaining string is also a palindrome. But at no point you are checking that.

So, with minimal changes in your code, the following solution will work, this will fail if an empty string is a passed as an argument.

def palindrome(string):
    print("palindrome called with:"+string)
    if(len(string)<=3):
        return string[0]==string[-1]
    else:
        if string[0] == string[-1]:
            res=palindrome(string[1:-1])
            print("palindrome returned:"+str(res))
            return res
        else:
            return False

Definitely, there are better ways of writing this.

def palindrome(s):
    return s == '' or (s[0]==s[-1] and palindrome(s[1:-1]))

All I have done is, further reduced your base case, by letting it make two more recursive calls.

Now, coming to the time complexity, which is same for both the codes.

In one function call, we are doing an O(1) operation of comparing the first and last character. And this recursive call is being done for at most n/2 times. n/2 because, in a string of length n, we are removing 2 characters in each call. Thus, the overall complexity will be O(n).(Just mind that, this ignores the string copying/slicing in every recursive call.)

Finally, you should avoid this recursively, as we are making a new string(at the time of slicing) before every recursive call.

def palindrome(s):
    def _palindrome(string, i, j):
        if i >= j:
            return True
        return string[i] == string[j] and _palindrome(string, i + 1, j - 1)
    return _palindrome(s, 0, len(s) - 1)

This will not make copy at every call. Thus, is definitely an O(n) solution.

Upvotes: 6

Related Questions