2
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 cannot analyze this algorithm. I must create a variable instrução
for example, and give a instrução++
in each if
, assignment, entry into the for
or since this algorithm has constant running time to say that it is O(1)? Or, just count how many times the recursion is called?
Related: Definition of the "Big O" notation
– Math