What is the time complexity of this reverse string function?-CodePudding

I came across this reverse string function:

l = [4,2,1,3,5]

def recReverseString(s):
    print('*')
    l = len(s)
    if l < 2:
        return s
    return recReverseString(s[int(l/2):])   recReverseString(s[:int(l/2)])

l2 = recReverseString(l)
print(l2)

It prints:

*
*
*
*
*
*
*
*
*
[5, 3, 1, 2, 4]

I prints 9 stars. So, I guess despite the halving operation, the time complexity is still O(n) and not O(log n), which is usually the case with most divide and conquer approaches. Am I right with this?

CodePudding user response：

We may as well assume that the length of the initial sequence is to the nth power of 2. Considering that len is O(1) and both twice slicing and connect two lists are O(n), we can list such an equation:

T(n) = 2T(n/2)   O(n)        (1)

Replace n with n/2, we can get:

T(n/2) = 2T(n/4)   O(n/2)    (2)

After logn times of replacement, we can get:

T(2) = 2T(1)   O(1)          (3)

Substituting equation 2 into equation 1, we have:

T(n) = 4T(n/4)   2O(n/2)   O(n) = 4T(n/4)   2O(n)

Substituting logn times repeatedly until equation 3, and the following can be obtained:

T(n) = nT(1)   logn * O(n) = O(n)   O(nlogn) = O(nlogn)

So the time complexity of your method is O(nlogn).

CodePudding user response：

Let T(n) represent the time complexity for the recReverseString function. Then we have the following equation

  // Assuming len(s) is O(1) but slicing would be O(n)
  T(n) = 2T(n/2)   O(n)

The solution for this equation is O(nlogn).

Take binary search as an example for a divide and conquer algorithm. In binary search the recursive call takes one half of the array. Hence the recursive equation in that case is

  T(n) = T(n/2)   1

The solution for this equation is O(logn)

CodePudding user response：

You cut in half at each recursive steps, but for half part you call the function, thus one call ==> two sub-calls.

No, divide and conquer has no complexity per se (or at least O(n)), it depend on what you make after dividing in parts... You can read divide and conquer or analysis of time complexity, read carefully the section about Master Theorem. What has complexity O(log(n)) is the binary search if the trees are somehow balanced. What is log(n) is the maximum height of the stack of the recursive calls.