1
def is_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

My first thought was that the complexity is O(n) because each recursive call removes 2 characters.

But then I thought of the slice's complexity. According to https://wiki.python.org/moin/TimeComplexity, the complexity of getting a slice is O(k), where k = number of elements in the slice. In is_palindrome, k = n - 2, then k = n - 4, then n - 6, etc. so I thought the complexity would be O(n^2) because each call has an (at worst) O(n) slice and there are n calls.

Which one is correct?

Frank Epps
  • 569
  • 1
  • 7
  • 21

1 Answers1

2

Imagine you have the classic O(n^2) algorithm: the double nested for-loop

for i in range(n):
    for j in range(n):
        #do_something

For every iteration of the outer loop, an entire iteration of the inner loop O(n) must be executed. This results in an O(n^2) runtime.

Now let's take a look at your algorithm - for every level of recursion, another O(n) algorithm (your slice) must be called - your recursive function is analogous to the outer loop, and your slice function is analogous to the inner loop.

Your recursion function is 

O(n/2) => O(n)

and your slice function is

O(t) where t < n

An alternate O(n) way to decide whether a string is palindrome is to simply iterate over the string once and in each iteration check opposite ends of the list. Remember the index accesses are O(1)

for i in xrange(len(s)/2):
  if s[i] != s[(len(s)-1)-i]:
    return False
return True
Martin Konecny
  • 57,827
  • 19
  • 139
  • 159
  • Your last sum is `O(n^2)`, not `O(n)`. – arshajii Jun 11 '14 at 02:31
  • Are you saying it's O(n^2)? Thanks! – Frank Epps Jun 11 '14 at 02:40
  • @arshajii - thanks - it didn't even make sense for me to sum it. – Martin Konecny Jun 11 '14 at 02:41
  • It's also O(n) in *space*, which is pretty unnecessary for a palindrome checker. Also, the link in your answer is a slightly more complicated question than simply checking if a string is a palindrome (that question asks about finding all palindromic *substrings*). – arshajii Jun 11 '14 at 02:47
  • Good eye. Added my own O(1) algorithm instead. – Martin Konecny Jun 11 '14 at 02:59
  • Thanks for the explanation. Since t < n, does it mean I can count the slice as O(1) negligible? – Frank Epps Jun 11 '14 at 03:00
  • No, the slice is not negligible. You need to account for it as O(n) – Martin Konecny Jun 11 '14 at 03:02
  • I feel compelled to ask, is there any possible use-case for a recursive palindrome checker *ever* being more appropriate than a non recursive solution other than to teach recursion? – Matt Coubrough Jun 11 '14 at 03:06
  • Unless your language is tail-call optimized (python is not), then you generally want to avoid recursion as you can easily cause a stack overflow, as well as function calls are costly (repeated stack allocations). In my opinion, recursion is generally a mental exercise. – Martin Konecny Jun 11 '14 at 03:08
  • Thank you so much. One last question: can I consider the algorithm as Theta(n^2) also? – Frank Epps Jun 11 '14 at 03:10