Complexity of string combination algorithm (as recursive)

Question

I have a method like the following:

How can I calculate the Big-O?

O(2ⁿ) or O(nⁿ)??

Thanks.

public static void combination(String str, int r) 
{

    int len = str.length();

    if (len == r) myList.add(str);
    if (len == 1) return;

    String newStr = null;
    for (int i = 0; i < len; i++) {
        newStr = str.substring(0, i) + str.substring(i + 1);
        combination(newStr, r);
    }
}

Take a look, maybe duplicate: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it — Igor, May 06 '11 at 21:01

score 1 · Answer 1 · answered May 06 '11 at 21:03

(since this is homework, just hints!)

Have you worked out what the code does yet? How much output does it produce for a given input?

That must be a lower-bound on the running time of the algorithm since there's no way you can run quicker than the number of outputs you must generate. Perhaps the easiest way would be to look at the size of the list for various inputs and use that as a basis.

score 1 · Answer 2 · answered May 06 '11 at 21:28

1

Here's my hint.

int n = str.length();

answered May 06 '11 at 21:28

Thomas Langston

3,743
1
25
41

score 1 · Answer 3 · answered May 07 '11 at 01:58

Try to transform the algorithm into an equation, something like X(n+1) = Function(X(n)) and resolve the equation.

If you can't, try with the initial case X(1) = Function(X(0)), then X(2) = Function(X(1)), etc... You will notice a pattern (and may be the answer is something different than O(2^n) or O(n^n)).

Just hints !!!

score 0 · Answer 4 · answered Apr 06 '16 at 20:55

For not-so-complex scenario, I use counter.

public class Combination {

    private static int count;

    public static void main(String[] args) {

        String[] inputs = new String[] {"12345", "1234", "123", "12", "1"};
        for(String input : inputs){
            count = 0;
            System.out.print("output for " + input + " is:");
            combination(input);
            System.out.println("\nCount for input:" + input + " is " + count);  
        }

    }

    private static void combination(String input) {
        combination("", input);
    }

    private static void combination(String prefix, String input) {
        System.out.print(prefix + " ");
        count++;
        int n = input.length();
        for(int i = 0; i < n; i++){
            combination(prefix + input.charAt(i), input.substring(i + 1));
        }
    }
}

The solution is indeed O(2^n)

Complexity of string combination algorithm (as recursive)

4 Answers4