How to come up with time complexity of backtracking problem?

Question

Given a list of lists, print list of lists where each list in the output is a combination of elements from the input lists.

For example: I/P -> [['a','b'],['c'],['d','e','f']]

o/p -> ['a','c','d'], ['a','c','e'], ['a','c','f'], ['b','c','d'], ['b','c','e'], ['b','c','f']

I have come up with the backtracking solution. Below is the code. However, i have difficulty in finding its time complexity. I think it's O(m^n), where m is the length of longest list in the given list of lists and n is the length of the given list. Is it right? How to find time complexity of backtracking problems like these?

def helper(lists, low, high, temp):
    if len(temp) == high:
        print temp
    for i in range(low, high):
        for j in range(len(lists[i])):
            helper(lists, i+1, high, temp+[lists[i][j]])

if __name__ == "__main__":
    l = [['a','b'],['c'],['d','e','f']]
    helper(l, 0, len(l), [])

Answer 1

Towards the complexity question:

If there are K lists each of length n_k, for k = 1,...,K, then the total number lists you need to output is n_1 * n_2 * ... * n_K (assuming order does not matter). Your bound clearly holds and is sharp when n_1 = n_2 = ... = n_k.

Alternatively, we can let N = n_1 + ... + n_k be the size of the disjoint union of input lists, and look for a bound in terms of N. For a fixed N, the worst case occurs when n_1 == n_2 etc., and we get O((N/k)^k). Maximizing over k, we find that k=N/e where e the Euler's number. So, we have O(e^(1/e)^N) ~ O(1.44^N).

As LeopardShark suggests, you can look up the itertools implementation of product for reference. It will not improve the asymptotic speed, but it will be more space efficient due to lazy returns.

A more tidy Python implementation could be as follows:

def custom_product(lsts):
    buf = [[]]
    for lst in lsts:
        buf = [b + [x] for b in buf for x in lst]
    return buf