I have a question about the complexity analysis of this code in Java:
public static int cont;
public static int recursive(int base,int numb,ArrayList<Integer> lista){
if(lista.size()>base) return 0;
if(numb<0 || numb>base-1) return 0;
ArrayList<Integer> newArray=new ArrayList<Integer>(lista.size()+1);
for(int i=0;i<lista.size();i++)
newArray.add(lista.get(i));
newArray.add(numb);
cont++;
recursive(base,numb-2,newArray);
recursive(base,numb-1,newArray);
recursive(base,numb+1,newArray);
recursive(base,numb+2,newArray);
return cont;
}
public static void main(String[] args){
int base=11;
ArrayList<Integer> test=new ArrayList<Integer>(base);
for(int i=1;i<11;i++){
recursive(base,i,test);
}
System.out.println("Números validos com digitos repetidos:"+cont);
}
I can not parse this algorithm. Should I create a instrução
variable for example, and give instrução++
in every if
, assignment, entry in for
or since this algorithm has constant execution time say it is O (1)? Or, just count how many times the recursion is called?