Counting complexity of algorithm - BigO

Question

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;
}
}

Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Matthew Brzezinski, Oct 31 '16 at 15:30
Interesting question - ordinarily I'd say "yes", but I'm going to have to think about how the if(j == i && j < list.length - 1) { j++; } bit affects this. — EJoshuaS - Stand with Ukraine, Oct 31 '16 at 15:33
@EJoshuaS I included that for second loop to skip value actually considered in the first loop, so it should look something like that O(n * ((n -1) * n)) — M Tomczynski, Oct 31 '16 at 15:45
@MattBrzezinski thank You for the link, I will edit/delete my question but if someone will give reasonably explanation for algorithm complexity regarding my code would it break rules if it stays as somewhat duplicate but providing possibly useful answer for other users? — M Tomczynski, Oct 31 '16 at 15:50
@EJoshuaS it's irrelevant what that does because of the `list.clone` in the second loop. That already adds another `O(n)` factor. — Vincent van der Weele, Oct 31 '16 at 17:15
@VincentvanderWeele ups, haven't thought about that one. Method calculateCoefficient(list) already adds up O(n) in the second loop, so with clone it should be O(n * (n - 1) * (n + n)) — M Tomczynski, Oct 31 '16 at 18:19

score 1 · Accepted Answer · answered Jan 23 '17 at 15:29

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.

Counting complexity of algorithm - BigO

1 Answers1