0

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

public List<String> getPermutations(String s){
    if(s.length()==1){
        List<String> base = new ArrayList<String>();
        base.add(String.valueOf(s.charAt(0)));
        return base;
    }

    List<String> combos = createPermsForCurrentChar(s.charAt(0),
                                    getPermutations(s.substring(1));

    return combos;
}
 private List<String> createPermsForCurrentChar(char a,List<String> temp){
    List<String> results = new ArrayList<String>();
    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) ?

2 Answers 2

2

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!)

2
  • So a function that is T(n) = n! . is O(n^2)?
    – smk
    Jan 30, 2013 at 16:26
  • 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, 2013 at 16:30
1

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

getPermutations(String)

is called is related to the call:

createPermsForCurrentChar(s.charAt(0),getPermutations(s.substring(1));

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).

6
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.