CODEWITHSUNDEEP
javaalgorithmcomplexity-theorybig-ocombinations
ProToneRCi
ProToneRCi

Reputation: 13

Complexity of string combination algorithm (as recursive)

I have a method like the following:

How can I calculate the Big-O?

O(2n) or O(nn)??

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);
    }
}

Upvotes: 1

Views: 1882

Answers (4)

Saurin
Saurin

Reputation: 39

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)

Upvotes: 0

J&#233;r&#244;me Verstrynge
J&#233;r&#244;me Verstrynge

Reputation: 59606

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

Upvotes: 1

Thomas Langston
Thomas Langston

Reputation: 3735

Here's my hint.

int n = str.length();

Upvotes: 1

Jeff Foster
Jeff Foster

Reputation: 44706

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

Upvotes: 1

Related Questions