2
$\begingroup$

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) < 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)<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?

$\endgroup$
  • $\begingroup$ I guess no, because work is done on the entire string. Hence the complexity should still be linear $\endgroup$ – Abhiroj Panwar Jan 4 '18 at 5:03
  • 1
    $\begingroup$ Coding questions and Python-specific questions are off-topic here. I don't think the question is answerable without knowing the running time it takes to construct a slice of a string in Python, which is beyond our scope. If you know that, please edit the question to specify that information. $\endgroup$ – D.W. Jan 4 '18 at 5:18
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Jan 4 '18 at 5:19
  • $\begingroup$ Do you know the shape and runtime cost of Mergesort? $\endgroup$ – Raphael Jan 4 '18 at 6:40
3
$\begingroup$
   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.

$\endgroup$
  • $\begingroup$ Exactly my point! $\endgroup$ – Abhiroj Panwar Jan 24 '18 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.