Complexity analysis

Question

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?

Answer 1

In analyzing the complexity of algorithms we must add the logical structures:

Conditional; Repetitions; Entrances - Exits; Recursion Call for other Functions;

Basically speaking, for any structure that has a repeating structure, be while, for, do, etc (no matter the language, Java, VB, Delphi, PHP, etc...) the algorithm receives the classification O(n 2) where n is the amount of input and or output of interaction in that code.

If we possess one is chained for example:

for (i = 0; i < n; i++){
    for (j = 0; j < n; j++){
    }
}

The complexity of the algorithm would be O(2n 2)

For conditional structures such as if, case, etc add one more in our analysis, Exp:

for (i = 0; i < n; i++){
    if(i > 10){
    }
}

The complexity of the algorithm would be O(1+n 2)

---

Today I’m short on time, tomorrow I edit the answer better (with books I used for the matter of analyzing the complexity of algorithms) to better form my answer, and to better analyze its algorithm