CODEWITHSUNDEEP
javaalgorithmtime-complexity
M Tomczynski
M Tomczynski

Reputation: 15714

Counting complexity of algorithm - BigO

I'm currently working my way up in the algorithmical problems. But I guess I still don't fully understand how to count algorithm complexity. I would say that my code have complexity O(n^3) because of three main loops inside them working on the data set, could someone confirm this or if I'm wrong show me on this bit of code how it should be counted?

public class BigOhN3 {

private Integer[] result;
private long time;


BigOhN3(Integer[] list) {
    long start = System.currentTimeMillis();
    int coefficientSum = calculateCoefficient(list);
    result = new Integer[list.length];

    //Main loop
    for(int i = 0; i < list.length; i++) {
        int coefficientSumIndexI = coefficientSum;
        for(int j = 0; j < list.length; j++) {
            Integer[] listIndexJ = list.clone();
            if(j == i && j < list.length - 1) {
                j++;
            }
            int a = listIndexJ[i];
            int b = listIndexJ[j];
            listIndexJ[i] = b;
            listIndexJ[j] = a;
            int coefficientSumIndexJ = calculateCoefficient(listIndexJ);
            if(coefficientSumIndexJ < coefficientSumIndexI) {
                coefficientSumIndexI = coefficientSumIndexJ;
                result[i] = coefficientSumIndexJ;
            }
        }
        if(result[i] == null) {
            result[i] = coefficientSum;
        }
    }
    time = System.currentTimeMillis() - start;
}

public long getTime() {
    return time;
}

private int calculateCoefficient(Integer[] list) {
    int sum = 0;
    for(int i = 0; i < list.length - 1; i++) {
        int item = list[i] - list[i + 1];
        if(item < 0) {
            item = item * (-1);
        }
        sum = sum + item;
    }
    return sum;
}

Integer[] getResult() {
    return result;
}
}

Upvotes: 2

Views: 144

Answers (1)

xenteros
xenteros

Reputation: 15842

It's O(n^3) indeed. But even if there was no most inner loop, it would be O(n^3) due to cloning a list (an array actually) takes at least O(n) as you need at least to read all elements. This means, that the complexity of the algorithm is:

O(n)*O(n)*(O(n)+O(n)) = O(n^3)

n times execute a loop a.
for each execution of a, execute loop b n times.
for each execution of b copy an array which takes O(n) and run the third loop which executes n times.

Upvotes: 1

Related Questions