Recursive functions from O(n) complexity to O(log n) For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each time?

For example, take this recursive reverse_string function ...

    def reverse_string1(s):
        if len(s) &lt; 2:
             return s
        return reverse_string1(s[1:]) + s[0]


... compared to this function that does the same string reversal:

   def reverse_string2(s):
       if len(s)&lt;2:
             return s
       mdpt = len(s)/2
       r1 = reverse_string2(s[:mdpt])
       r2 = reverse_string2(s[mdpt:])
       return r2 + r1 


Does the latter function successfully reduce the runtime complexity from linear to logarithmic?
r1 = reverse_string2(s[:mdpt])
   r2 = reverse_string2(s[mdpt:])


Here you go in recursion twice. In both recursions you will again recurse twice, etc, which makes $2*2*2... = O(2^{\log n}) = O(n)$. So the complexity is the same.