What is the complexity of a function that has a loop inside a recursion function
im trying to analyze the complexity of this code. i figured its o (n ^ 2) because for loop we take o (n) inside recursion function which takes o (n) o (n) * o (n) = o (n ^ 2) however i am 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);
}
}
source to share
You are correct that total complexity is a product of nested complexity and that the permutation function is called n times, where n is the length of the string, and the loop is also called n times, resulting in n ^ 2 loop calls. However, you also need to look at the complexity of the code inside the loop, especially replaceFirst
and insert
decide if their execution time depends on the length of the line and is multiplied by that. Since I suspect this is a homework question, I leave that to you.
source to share