# What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class.

I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + list2. I still want to know the answer for my question - it seemed important to my professor that we learn how to write good recursive function. The time complexity of a well written recursive merge function, according to him, is O(n).

The function receives two ordered lists and merges them into another ordered list. I would say that it runs in O(n), but, at the same time, I feel that my function is not well written; I guess I can't evaluate this more precisely because I don't quite know everything that happens behind the scenes to the Python's built-in functions I use.

def mergeR(l1, l2):
lfinal = []

if not l1:
return l2
if not l2:
return l1

if l1[0] < l2[0]:
lfinal.append(l1.pop(0))
elif l1[0] == l2[0]:
l2.pop(0)
else:
lfinal.append(l2.pop(0))

lfinal.extend(mergeR(l1, l2))

return lfinal

• The answer depends on the inner workings of python, so in principle we can't really tell. But you can try to do experiments and see whether the running time seems linear or not. – Yuval Filmus May 10 '15 at 12:57
• I removed your test cases, since they don't seem to be relevant to the question you're asking. – David Richerby May 10 '15 at 13:01
• The answer to the question as written does indeed depend on the python internals. One way to proceed would be to just point-blank assume that the python routines youse run in constant time. An alternative would be to use an oracle model, which amounts to saying, "I've no idea how long those python routines take but I'll keep track of how many steps my own code makes and how many times I call the python routines." – David Richerby May 10 '15 at 13:06