Consider how many calls you're doing. At the first level of the recursion you'll do 2 calls. For each of those you'll do two more calls. Etc ... This means that at level i
of the recursion you'll have made a total of O(2^i)
function calls.
How many levels of the recursion are there? This is just the height of a binary tree with n
elements, which is O(log_2 n)
.
So by the time you reach all the leaves of the recursion you will have done O(2^(log_2 n)) = O(n)
function calls.
--
Another way of looking at it is that you eventually have to piece back together the entire list, so how could you possibly do that in less than O(n)
time?