Q:

Backtracking worst time complexity of this recursive function

public static void generateWords(List<List<String>> words) {
    generateWordsHelper("", words);
}

public static void generateWordsHelper(String prefix, List<List<String>> words) {
    if (words.isEmpty()) {
        System.out.println(prefix);
        return;
    }
    for (int i = 0; i < words.size(); i++) {
        for (int j = 0; words.size() > 0 && j < words.get(i).size(); j++) {
            generateWordsHelper(prefix + words.get(i).get(j), words.subList(i+1, words.size()));
        }
    }
}

Hi folks,
What would be the worst time complexity of this function, and how do I compute it. Because it's back-tracking, I feel like it's O(2^n), but I have no way of proving it, or explaining why that's the case.

A:

It's hard to express this in terms of the total number of Strings in the list, because there are two variables involved: the number of List<String> elements of the outer list, and the number of String elements in each List<String>.
To simplify, suppose we assume that m = words.size(), and each List<String> has k elements.  (In real life, all the List<String>s won't necessarily have the same size.)  Then the total number of Strings in the list is n = mk.  Let's count the total number of times generateWordsHelper is called.  If m = 0, we call it once, but the function never calls itself recursively.  If m = 1, the function is called once, and then we call it recursively k times (because of the int j loop), but each time we call it, it will be called on a sublist of size 0.  If m = 2, the function is called once, and then the function calls itself recursively k times with a sublist of size 1, and k times with a sublist of size 0 [but not in that order]; if m = 3, it calls itself recursively k times with a sublist of size 2, again with a sublist of size 1, again with a sublist of size 0.  So we can see the pattern.  If we denote f(m) to be the total number of times generateWordHelper is called when the initial size is m, then
f(0) = 1
f(m) = 1 + k * f(m-1) + k * f(m-2) + ... + k * f(0)
which works out to
f(0) = 1
f(1) = 1 + k
f(2) = 1 + 2k + k2
f(3) = 1 + 3k + 3k2 + k3
or
f(m) = (k+1)m
So I think that's the formula you're looking for: O((k+1)m).  I don't think this can be simply expressed in one variable n, where n is the total number of strings.  If each List<String> contains one element, so that k = 1 and n = m, then the number of recursive calls is indeed O(2n)--or actually, exactly 2n.  If we say the average size of each List<String> is z, then we'll probably get close by using the formula with k = z and m = n/z, so that the complexity is O((z+1)n/z).
Note, though, that I've computed "complexity" only in terms of the number of times the recursive method is called.  This doesn't account for the String operation prefix + words.get(i).get(j) possibly being proportional to one of the variables.

