Time complexity of python code for finding the lon

问题:

I am preparing for some coding interviews and came up with a solution to the following problem:

"Find longest word that can be made of other words in a list of words".

I have a hard time figuring out the time complexity of my algorithm. It would be great, if you can help me to figure out the time complexity of the following code.

It is more than n² (n⋅log n for sorting, number_of_words ⋅ word_length + recursion), but not sure how to calculate the exact complexity due to recursion part.

def valid_pair(a,b, words):
    return  a in words and b in words

def valid_word(word, words):
    for i in range(len(word)):
        left, right = word[:i], word[i:]
        valid =  valid_pair(left, right, words)
        if valid:
            return valid
        elif left in words:
            return valid_word(right, words)

    return False


words = ["cde","abcde","bcd","c","d","e","a"]

words = sorted(words, key = len, reverse = True)
for w in words:
    if valid_word(w, words):
        print w
        break

回答1:

Let n be the number of words in the list and m the length of the longest word.

The for-loop iterates over the words until valid_word returns true. The worst case would be, that non of the words can be concatenated from other words in the list. So this gives you a factor n.

valid_word iterates over all characters in a word and calls valid_pair which has the complexity O(f), where f = f(n,m) is the complexity of the in operator. (I don't know, how it is implemented). If for every character left is in words, but right is not, valid_word is called recursively m times, resulting in this formula:

T(m) = f + Σi=1,...m-1 T(m-i) < f + (m-1) ⋅ T(m-1) < m!⋅f 

So valid_word is in O(m!⋅f(n,m)) (this can be improved).

The over all complexity is O(n⋅m!⋅f(n,m) + n⋅log(n)). This is an upper bound, so maybe you can improve this, by showing that it is not possible to have an input that forces the algorithm to do all the steps.

But think of an input like this (withe spaces are only for better readability)

words = ['ab ac ad ae','ab ac ad af', ... , 'ab ac ad az',
         'ab ac ad', 'ab ac', 'ab']

Non of these words can be concatenated from the others, but the algorithm has to try many combinations. This examples can be improved and extended.