Big O Notation for the permutations of a list of words

Question

What would be the big O notation of the length of the list of permutations of the characters of a list of words of lenght n?

I just do not know how to express that because it would be like n! for each word where n is the characters of that word but O(n!) is just the complexity of a single word, not a list of n words.

Also, every word may have different sizes.

An example:

Let's say that I have the words "abc", "abcd" and "abcde". If I have to create the permutations of each word, I would end up with a list of lists of strings with lengths of 6, 24 and 120 i.e. the permutations of "abc" will be in the first list, the permutations of the second word will be in the second and so on and so on.

If I use an permutation iterator, how much time will it take to generate all those lists?

Answer 1

Since BigO represents an upper bound then you can safely say that there are O(k*n!) strings where n is the length of the longest input word (since in the worst case all the strings will have the same length then there will be exactly k*n! permutations, in a better case with variable lengths the number will be < k*n! but the notation O(k*n!) still holds).

If you have some additional information regarding the distribution of those lengths we can try to do a tighter bound :-)

@Edit: as @Aron pointed out this is a pretty (I'm not gonna get very formal here) tight upper bound if you do not have repeating chars. With repeating chars it's still a valid upper bound but a tighter bound would be O(k*a^n) where a is the size of our alphabet (26 if you are using English, more than 110,000 if you are using Unicode) this will eventually be tighter than O(k*n!). This holds because at each of the n slots in a word you can place one of a characters and notice that with repeating chars a might be smaller (even much smaller) than n.