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

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