Analysis of complexity

Question

Analysis of complexity

Navigation

#1 by (1 votes)

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 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?

java

asked by anonymous 19.04.2015 / 05:12

1 answer

Add a plot and image in matlab Check if you have the string and include your tags

score 1 · Answer 1

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

Conditional; Repetitions; Inputs - Outputs; Recursiveness; Calling other functions;

Basically speaking, for every structure that has a repeat structure, be while , for , do , etc (no matter the language, Java, VB, Delphi, PHP, etc ...) o algorithm receives receives the rank O (n ^ 2) where n is the input quantity and or interaction output in that code.

If we have a string 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 like if , case , etc. we add another one 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 have a short time, tomorrow I edit the answer better (with books that I used for the matter of analysis of algorithmic complexity) to better shape my response, and to better analyze your algorithm