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.