# Time complexity of merging two lists while preserving order

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.

• What are the complexities of append and pop ? Mar 3, 2022 at 8:46
• Notice how this is equivalent to the counting the number of north-east lattice paths from $(0,0)$ to $(m,n)$. Or $(n,m)$ Mar 3, 2022 at 10:01
• @YvesDaoust append and pop are both O(1)
– sam
Mar 4, 2022 at 0:33
• pop can be O(n). And what about the cost of implied memory allocation/deallocations ? Mar 4, 2022 at 8:37
• "as we have two choices for every iteration": mh, no. After a number of iterations, one of the lists will exhaust and only one choice remains. This may sound unimportant, but it changes the complexity. Mar 28 at 8:08

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.