def check_palin(word):
    for i in range(len(word)//2):
        if word[i] != word[-(i+1)]:
            return False
    return True

I guess this is a bit more efficient solution as it iterates over half of the string and returns False whenever the condition is violated. But still the complexity would be O(n)

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Even worse is doing so in a loop, because this has to happen ever time. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).

But here you can just use the fact that strings can be sliced and you can specify a negative step:

def reverse_g(s):
    return s[::-1]

Here is a timing comparison for random strings of length from one up to 1M characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is almost a hundred thousand times slower.

The reverse_s function uses the reversed built-in, as suggested in the (now deleted, so 10k+ reputation) answer by @sleblanc and assumes you actually need the reversed string and not just an iterator over it:

def reverse_s(s):
    return ''.join(reversed(s))

The reverse_b function uses the C implementation, compiled with -O3, provided in the answer by @Broman, with a wrapper to create the string buffers and extract the output:

from ctypes import *

revlib = cdll.LoadLibrary("rev.so")
_reverse_b = revlib.reverse
_reverse_b.argtypes = [c_char_p, c_char_p, c_size_t]

def reverse_b(s):
    stri = create_string_buffer(s.encode('utf-8'))
    stro = create_string_buffer(b'\000' * (len(s)+1))
    _reverse_b(stro, stri, len(s) - 1)
    return stro.value.decode()

In the no interface version, just the call to _reverse_b is timed.

reversed(some_list) always takes about 120ns to finish on my machine, which is a clear sign of O(1) time complexity. This is because this function does not actually change any values, it just returns a list_reverseiterator, which iterates the list backwards. This object is very similar to a normal generator, as it its elements get consumed, when you are, for example, calling list on it:

In [10]: a = [i for i in range(5)]

In [11]: b = reversed(a)

In [12]: b
Out[12]: <list_reverseiterator at 0x7f11fe3615b0>

In [13]: list(b)
Out[13]: [4, 3, 2, 1, 0]

In [14]: b
Out[14]: <list_reverseiterator at 0x7f11fe3615b0>

In [15]: list(b)
Out[15]: []

Without even trying to bench it (you can do it easily), reverse_1 would be dead slow because of many things:

• loop with index
• constantly adding character to string, creating a copy each time.

So, slow because of loop & indexes, O(n*n) time complexity because of the string copies, O(n) complexity because it uses extra memory to create temp strings (which are hopefully garbage collected in the loop).

On the other hand s[::-1]:

• doesn't use a visible loop
• returns a string without the need to convert from/to list
• uses compiled code from python runtime

So you cannot beat it in terms of time & space complexity and speed.

If you want an alternative you can use:

''.join(reversed(s))

but that will be slower than s[::-1] (it has to create a list so join can build a string back). It's interesting when other transformations are required than reversing the string.

Note that unlike C or C++ languages (as far as the analogy goes for strings) it is not possible to reverse the string with O(1) space complexity because of the immutability of strings: you need twice the memory because string operations cannot be done in-place (this can be done on list of characters, but the str <=> list conversions use memory)

The python page on time-complexity shows that slicing lists has a time-complexity of O(k), where "k" is the length of the slice. That's for lists, not strings, but the complexity can't be O(1) for strings since the slicing must handle more characters as the size is increased. At a guess, the complexity of slicing strings would also be O(k). We can write a little bit of code to test that guess:

import time

StartSize = 2097152

size = StartSize
for _ in range(10):
    # create string of size "size"
    s = '*' * size

    # now time reverse slice
    start = time.time()
    r = s[::-1]
    delta = time.time() - start

    print(f'Size {size:9d}, time={delta:.3f}')

    # double size of the string
    size *= 2

This uses a simple method of timing. Other tools exist, but this is simple. When run I get:

$ python3 test.py
Size   2097152, time=0.006
Size   4194304, time=0.013
Size   8388608, time=0.024
Size  16777216, time=0.050
Size  33554432, time=0.098
Size  67108864, time=0.190
Size 134217728, time=0.401
Size 268435456, time=0.808
Size 536870912, time=1.610
Size 1073741824, time=3.192

which shows the time doubles when doubling the size of the string for each reverse slice. So O(n) (k == n for whole-string slicing).

Edit: spelling.

Let T(n) represent the time complexity for the recReverseString function. Then we have the following equation

  // Assuming len(s) is O(1) but slicing would be O(n)
  T(n) = 2T(n/2) + O(n)

The solution for this equation is O(nlogn).

Take binary search as an example for a divide and conquer algorithm. In binary search the recursive call takes one half of the array. Hence the recursive equation in that case is

  T(n) = T(n/2) + 1

The solution for this equation is O(logn)

No, it is O(n log n).

String concatenation is linear. Each + in the expression left_half + right_half takes O(l+r) time, where l = len(left_half) and r = len(right_half).

• You concatenate two length n/2 strings 1 time.
• You concatenate two length n/4 strings 2 times.
• You concatenate two length n/8 strings 4 times.
• ...
• You concatenate two length 4 strings n/8 times.
• You concatenate two length 2 strings n/4 times.
• You concatenate two length 1 strings n/2 times.

Each step takes O(n) and there are O(log n) steps, leading to an overall time complexity of O(n log n).

Footnote: The string slices num[n:] and num[:n] also have linear complexity. Creating a slice of length k is O(k). Accounting for these costs doesn't change the overall analysis.