Palindrome? What is the time complexity?

When I learn English, I found that English has an interesting concept - Palindrome. Palindrome is the word/sequence that is the same when you read forward or backward, like racecar, refer, level, …

And when I learn python programming, there is the problem that we need to check a word (string) is a palindrome or not. It’s easy, I think. I can do it seamless even at the first try.

def is_palindrome(word: str) -> bool:
    return word == word.reverse()        

It’s a single line function, yeah it really is:

is_palindrome = lambda word: word == word.reverse()        

And it’s clear O(n) in the time complexity due to the reverse() built-in function would be O(n) with n is the length of the word. Easy pz, and we even have a built-in function.

The story should end here but have you ever thought about what if the sequence word is an int (base 10 of course)? I’ve never doubt. It must still be O(n)!

It is O(n) though, but how to code it? Easy right? Only need to cast the integer to string and the rest is just the same! We have str() function and it’s a built-in one.

def is_palindrome(number: str) -> bool:
    word = str(number)
    return word == word.reverse()        

I was really confident that the second function only take O(n) too, initially thought is that the cast line added only O(1) or O(n). This was a big mistake. In python, different from many other languages that int is a fixed length data type (can be 2 bytes, 4 bytes,… but is a fixed number), an integer in python can take an arbitrary length only be bounded by the computer resources [1] .

So number argument can be any size.

I decided to read the source code of CPython [2] to know how the str function work. There are many interesting things in the code that convert an int to a str in python.

1. First python will do some check for security purpose. It will raise error to prevent DoS attack [3]
2. Then the actual code converts int to str: python will check if it is negative (for adding '-' character), estimate how many characters need in string in order to allocate memory.
3. Next, python will convert the underlying array of integer to array of base 10 number. This operation takes O(size_a*size_dec) in time complexity in which size_a is the number of digits in variable part (binary form) and size_dec is number of digits in decimal form. The number of digits is calculated by log(number, base=b) so the final time complexity will be O(log(number, base=2) * log(number, base=10)) ~ O(log(number)**2) ~ O(n**2) with n is number of digits of number argument.
4. Finally, it will calculate exact size of string needed and write number base 10 to string (from right to left) and add the minus (-) sign if needed.

Ah ha! Because of step 3 converting big number (python's int) to string in python take O(n**2) with n is number of digits of the input. So, the line word = str(number) will be that complexity. It’s quadratic in the number of digits not linear.

Oh well, now can we reduce the time complexity??I tried to code the new solution:

def is_palindrome(number: int) -> bool:
    # Clearly if the number is negative, it is NOT a palindrome
    if number < 0:
        return False

    org_number = number
    reversed_number = 0

    while number > 0:
        reversed_number = 10 * reversed_number + number % 10
        number //= 10

    return reversed_number == org_number        

The loop will take log(number, base=10) times so the time complexity should be O(n) where n is number of digits of the integer in base 10.

After I find out the problem, I immediately think what @Kathryn Schulz say in her TED talk [4], how do you experience being wrong? Is it embarrassment or shame? Not quite. Embarrassment or shame typically arise when you're aware of your error. When you're actually wrong, it's a peculiar feeling of being right. Sometimes, when dealing with familiar problems, we allow our brain's autopilot to make judgments, and one day, this can lead to inaccuracies. The more you learn, the more you realize the vast expanse of what you don't know.

What do you think about this? Am I still missing something here? I am not feeling right right now, I am confused.

?

?

[1] This is a good article about the implementation of CPython big number: https://tenthousandmeters.com/blog/python-behind-the-scenes-8-how-python-integers-work/

[2] The code converts decimal based number to string: https://github.com/python/cpython/blob/a03a09e068435f47d02649dda93988dc44ffaaf1/Objects/longobject.c#L1689

[3] CVE-2020-10735: Prevent DoS by large int<->str conversions: https://github.com/python/cpython/issues/95778

[4] On being wrong: https://www.ted.com/talks/kathryn_schulz_on_being_wrong?language=en