Time complexity of merging two lists while preserving order

Question

I have two lists l1 and l2 of possibly unequal sizes (say, m and n). I wrote an algorithm to find out all ways l1 and l2 can be merged while preserving their order.

l1 = ["NYC", "LA"]
l2 = ["A", "B"]

output:
[['NYC', 'LA', 'A', 'B'],
 ['NYC', 'A', 'LA', 'B'],
 ['NYC', 'A', 'B', 'LA'],
 ['A', 'NYC', 'LA', 'B'],
 ['A', 'NYC', 'B', 'LA'],
 ['A', 'B', 'NYC', 'LA']]

NYC always comes before LA. A always comes before B.

Basic idea of algorithm: Append one item from l1 to temp, recurse on remaining part of the lists. Do the same for l2.

Code (python3):

def merge(l1, l2):    
    temp = [] # temporary buffer 
    res = [] # final result
    mergeHelper(l1, 0, l2, 0, temp, res)
    return res

def mergeHelper(l1, start1, l2, start2, temp, res):
    if start1 >= len(l1) and start2 >= len(l2):
        res.append(temp.copy())
        return

    if start1 < len(l1):
        temp.append(l1[start1])
        mergeHelper(l1, start1+1, l2, start2, temp, res)
        temp.pop()

    if start2 < len(l2):
        temp.append(l2[start2])
        mergeHelper(l1, start1, l2, start2+1, temp, res)
        temp.pop()

Question: What's the time/space complexity? I suspect it might be $O(2^{n+m})$ as we have two choices for every iteration.

I figured out the recurrence relation is: T(m,n) = 1 + T(n-1, m) + 1 + T(n, m-1) but unable to reduce it further.

Answer 1

The number of ways to combine an ordered list of size $n$ and an ordered list of size $m$ into one ordered list of size $n+m$ in a way which keeps the order of both lists is given by the binomial coefficient $$\binom{n+m}{n}$$ The time complexity of your procedure depends on various implementation details.