Reversing a String: Is this O(log n) time complexity?-CodePudding

I was doing this leetcode question which asks to reverse an integer. I wrote this method to convert int to string and reverse using divide-and-conquer recursion technique. I want to know is this O(log n) time complexity? (n being the number of characters in String).

def __reverse_recur__(self, num: str):
    N = len(num)
    # if we are reduced to only a single char, return it
    if N == 1:
        return num
    else:
        n = int(N / 2)  # index to split string from middle
        
        # concatenate the recursion result as follows:
        # recurse on the right-part of the string to place it as the left half of the concatenation
        left_half = self.__reverse_recur__(num[n:])
        # recurse on the left-part of the string to place it as the right half of the concatenation
        right_half = self.__reverse_recur__(num[:n])

        # return the concatenated string
        return left_half   right_half

CodePudding user response：

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.}