CODEWITHSUNDEEP
algorithmtime-complexity
smk
smk

Reputation: 5842

Time complexity for algorithm

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

Upvotes: 0

Views: 506

Answers (2)

thang
thang

Reputation: 3466

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

Upvotes: 2

AndyG
AndyG

Reputation: 41100

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

Upvotes: 1

Related Questions