Take the 2-minute tour ×

I'd like to know the Big Oh for the following algorithm

public List<String> getPermutations(String s){
        List<String> base = new ArrayList<String>();
        return base;

    List<String> combos = createPermsForCurrentChar(s.charAt(0),

    return combos;
 private List<String> createPermsForCurrentChar(char a,List<String> temp){
    for(String tempStr : temp){
        for(int i=0;i<tempStr.length();i++){
            String prefix = tempStr.substring(0, i);

            String suffix = tempStr.substring(i);

            results.add(prefix + a + suffix);

    return results;

Heres what I think it is getPermutations is called n times , where n is length of the string. My understanding is that createPermutations is O(l * m) where l is the length of list temp and m is the length of each string in temp.

However since we are looking at worst case analysis, m<=n and l<= n!. The length of the temp list keeps growing in each recursive call and so does the number of characters in each string in temp.

Does this mean that the time complexity of this algorithm is O(n * n! *n). Or is it O(n * n * n) ?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Well, I will just write this up as an answer instead of having a long list of comments.

Denote the run time of getPerm on string of length n as T(n). Observe that inside getPerm, it calls getPerm(string length n-1), so clearly

T(n)=T(n-1) + [run time of createPerm]

Note that createPerm has 2 loops that are nested. The outer loop iterates through the size of the result of getperm(string of length n-1) and the inner loop iterates through n-1 (length of individual strings). The result of getPerm(string of length n-1) is a list of T(n-1) strings. From this, we get that

[run time of createPerm] = (n-1) T(n-1)

Substituting this into the previous equation gives

T(n) = T(n-1) + (n-1) T(n-1) = n T(n-1)

T(1) = 1 from the exit condition. We can just expand to find the solution (or, alternatively, use Z-transform: Can not figure out complexity of this recurrence). Since it is a simple equation, expanding is faster:

 T(n) = n T(n-1)
      = n (n-1) T(n-2)
      = n (n-1) (n-2) T(n-3) ....
      = n (n-1) ... 1
      = n!

So T(n) = n!

Exercise: prove this by induction! :p

Does this make sense? Let's think about it. We are creating permutations of n characters: http://en.wikipedia.org/wiki/Permutation.

EDIT: note that T(n)=n! is O(n!)

share|improve this answer
Thanks for the explanation! –  AndyG Jan 30 '13 at 16:25
So a function that is T(n) = n! . is O(n^2)? –  smk Jan 30 '13 at 16:26
no n! is O(n!), which is faster growth rate than O(n^2) –  thang Jan 30 '13 at 16:28
Much faster too: O(n^2) is typically 1+2+3+4+...+n, while O(n!) is multiplicative: 1*2*3*4*...*n. –  AndyG Jan 30 '13 at 16:30
add comment

I'm not the best with combinatorics, but I think it's O(n^3) where n is the number of characters in your string.

My logic is this: The number of times that


is called is related to the call:


On the first call you pass arguements (charAt(0), substring of length s.length-1), then (charAt(1), substring of length s.length-2)... for O(n) calls.

What's more important is the # of elements in List temp each time we enter createPermsForCurrentChar.

First, let's analyze the function as a standalone thing: Let's say there are k elements in List<String> temp, and they have monotonically increasing lengths, denoted by L=current length, beginning with L=1 and ending with L=k.

The outer-for loop will iterate k times, this is easy. The inner for loop will iterate L times. Our complexity is O(k"L"). L is in quotation marks because it changes each time, let's see what it looks like: First outer loop iteration, the inner loop executes once. Second outer loop ieration, the inner loop executes twice, and so on until the inner loop executes k times giving us 1+2+3+4+...k = O(k^2).

So createPermsForCurrentChar is O(k^2) complexity, where k is the number of elements in List<String> temp (and also the size of the longest string in temp). What we want to know now is this - How many elements will be in List<string> temp for each call?

When we finally reach the base case in our recursion, we're passing the second last character of our string, and the last character of our string to createPermsForCurrentChar, so k=1. It will create a single string of length O(k). This allows the next execution to pop off the stack and call createPermsForCurrentChar again, this time with k=2. Then k=3, k=4, k=5, etc.

We know that createPermsForCurrentChar is being called O(n) times due to our recurrence relation, so k will eventually = n. (1 + 2 + 3 + ... + n) = O(n^2). Taking into account the complexity of createPermsForCurrentChar, we get (1^2 + 2^2 + 3^2 + ... n^2) = (1/3)n^3 + (1/2)n^2 + (1/6)n (from http://math2.org/math/expansion/power.htm).

Since we only care about our dominating value, we can say that the algorithm is O(n^3).

share|improve this answer
this answer is wrong. to see why, for a string of length L, how many outputs does the function generate? is this bigger or smaller than c L^3? to get the right answer, first, write down the recurrence relation that describes the run time. –  thang Jan 30 '13 at 8:24
@thang: Thanks for the comment, I see what you mean, in the recurrence relationship, the number of outputs grows as the series (1^2) + (1^2 + 2^2) + (1^2 + 2^2 + 3^2) + ... + (1^2 + 2^2 + 3^2 + ... n^2). Is this right? –  AndyG Jan 30 '13 at 15:30
i think i would just say that the run time for a string of length n is T(n). I know that T(n) = getPerm(for n-1) + createPerm(for output of get perm). getPerm(n-1) is clearly T(n-1) and it returns a list of T(n-1) element of strings with length (n-1) each. i can then use that to express createPerm in terms of T(n-1) and (n-1). this will give a complete recurrence relation. solve the recurrence relation to get the answer in the form of T(n) as a function of just n. –  thang Jan 30 '13 at 16:11
@thang: So what you're saying is T(n) = T(n-1) + T(n-1)*(n-1) = T(n-1)(1 + (n-1)) = nT(n-1) = n * (n-1) * (n-2) ... * 1 = n! –  AndyG Jan 30 '13 at 16:21
For a list of string of length l and for each string in that list having k characters , the for loop is executed (k+1) * l times. –  smk Jan 30 '13 at 16:22
show 1 more comment

Your Answer


