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"]

[['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):

    if start1 < len(l1):
        mergeHelper(l1, start1+1, l2, start2, temp, res)

    if start2 < len(l2):
        mergeHelper(l1, start1, l2, start2+1, temp, res)

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.

  • $\begingroup$ What are the complexities of append and pop ? $\endgroup$ Mar 3, 2022 at 8:46
  • $\begingroup$ Notice how this is equivalent to the counting the number of north-east lattice paths from $(0,0)$ to $(m,n)$. Or $(n,m)$ $\endgroup$
    – droptop
    Mar 3, 2022 at 10:01
  • $\begingroup$ @YvesDaoust append and pop are both O(1) $\endgroup$
    – sam
    Mar 4, 2022 at 0:33
  • $\begingroup$ pop can be O(n). And what about the cost of implied memory allocation/deallocations ? $\endgroup$ Mar 4, 2022 at 8:37
  • $\begingroup$ "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. $\endgroup$ Mar 28 at 8:08

1 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.

  • $\begingroup$ Could you please give a little bit more details on how you arrived at this? $\endgroup$
    – sam
    Mar 4, 2022 at 0:32
  • $\begingroup$ It’s basic combinatorics. Once you chose the positions of the elements of the first list inside the combined list, everything else is determined (including which element of each list goes to with position). $\endgroup$ Mar 4, 2022 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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