Big O for Palindrome Checker Python

Question

There are a few different solutions to the classic Palindrome Question. One of them involves reversing the string and comparing the original string to it another involves comparing first and last letters of the string and then recursively doing the same for the inner string.

For the first approach, is invoking string[::-1] an O(n) operating or an O(n^2) one? I believe that appending a char to a string is an O(n) operation (while appending to a list is O(1)), so does setting reversedString = string[::-1] treat string as a string or as an array?

For the recursive approach, if my solution is:

    if len(string) <= 1:
        return True

    return (string[0] == string[-1]) and check_palindrome(string[1:-1])

does this take O(n) space or O(n^2) space? I know O(n) space is taken up by the recursive calls, but I'm thinking that on each stack the string is stored, so would that make it O(n*n) = O(n^2) space?

Thanks!

Pretty sure string-reversal does not work by repeatedly appending strings to a temp string, but you can test by timing the reversal of, say, a 10k char string, and a 20k char string. About the recursive: Yes, O(n²) space (and, in fact, time, too for constructing those slices) seems about right. — tobias_k, Jul 22 '22 at 13:39
In regards to reversing a string: [Is the time-complexity of iterative string append actually O(n^2), or O(n)?](https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on) — matszwecja, Jul 22 '22 at 13:41
Awesome, @tobias_k, if you make your comment an answer I'll accept it! — Python Developer, Jul 22 '22 at 15:00

score 1 · Accepted Answer · answered Jul 22 '22 at 16:02

About the first part: string[::-1] is O(n), not O(n²). I am not sure how exactly it is done, internally, but it definitely does not repeatedly append each character to a sequence of growing immutable strings. Sometimes, things like this can easily be checked in Python itself by timing the execution:

>>> s1 = str(list(range(1000)))                                             
>>> s2 = str(list(range(10000)))                                            
>>> len(s1), len(s2)                                                        
(4890, 58890)
>>> %timeit s1[::-1]                                                        
3.03 µs ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit s2[::-1]                                                        
34.4 µs ± 60.6 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

About the second part: This particular recursive algorithm should indeed be O(n²) in both time and space. The main problem here is, of course, repeatedly creating the ever-smaller slices of the string (which, according to this question, creates actual copies of the string and not just a "view" on part of the string). Stacked on top of each other, those would have the shape of a triangle, i.e. not quite "quadratic" but still O(n²). The case would be different, though, if instead of slicing, you'd pass the start- and end-index (or just the offset from both start and end) as additional parameters, then there is no slicing and Python would just have to store a reference to the original string on the stack.

Big O for Palindrome Checker Python

1 Answers1