what is the complexity of function that have loop inside recursion function

Question

im trying to analysis the complexity of this code . i predicated that its o(n^2) because for loop take a o(n) inside a recursion function thats take o(n) o(n) * o(n) = o(n^2) however im not sure .

public class main 
{

    static Set<String> setString = new HashSet<>();

    public static void main(String[] args) 
    {
        // TODO Auto-generated method stub
        main m = new main();
        m.permute("sanad", 0);
        for(String s : setString)
        {
            System.out.println(s);
        }

    }


    public void permute(String str , int i )
    {
        if (i>=str.length())
        {
            return;
        }


        for(int j = 0 ; j < str.length();j++)
        {
            StringBuilder b = new StringBuilder(str. replaceFirst(String.valueOf(str.charAt(i)), ""));
            b.insert(j,str.charAt(i));
            setString.add(b.toString());
        }

        permute(str, ++i);
    }

}

Are you attempting to put all permutations of a string into your hashset? — Jayson Boubin
– Jayson Boubin, Commented Jun 7, 2017 at 15:54
Is it guaranteed that the string will include only unique characters? If not, then your program is incorrect. — RealSkeptic
– RealSkeptic, Commented Jun 7, 2017 at 16:01
@JaysonBoubin yes . but what i am thinking to solve this question on o(n) — user3512497
– user3512497, Commented Jun 7, 2017 at 18:00
Nope... if a program has to create N! solutions, then it is O(N!). It has to at least write each solution once somewhere... — RealSkeptic
– RealSkeptic, Commented Jun 7, 2017 at 19:00

Konrad Höffner · Accepted Answer · 2017-06-07 15:57:39Z

6

You are correct in that the total complexity is the product of the nested complexities and that the permute function is called n times, where n is the length of the string, and the loop is called n times as well, leading to n^2 calls of the loop . However you also have to look at the complexity of the code inside the loop, especially replaceFirst and insert, decide, if their runtime depends on the length of the string, and multiply with that as well. As I suspect this is a homework question I leave this to you.

answered Jun 7, 2017 at 15:57

Konrad Höffner

12.6k20 gold badges75 silver badges139 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3512497 Over a year ago

thanks ... no its not a homework what i need to do is to solve this question using o(n) complexity

Collectives™ on Stack Overflow

what is the complexity of function that have loop inside recursion function

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related