CODEWITHSUNDEEP
javabig-o
Nabil Zubair
Nabil Zubair

Reputation: 23

Why is this O(N^3) and not O(N^4)?

public static int g(LinkedList<Integer> list) {
    int t = 0;

    for (int i = 0; i < list.size(); i++) {
        int tgt = list.get(i);

        for (int j = i + 1; j < list.size(); j++) {
            if (list.get(j) == tgt) 
                t += list.get(j);
        }
    }

    return t;
}

Shouldn't the if statement make the complexity O(N^4)?

Upvotes: 2

Views: 83

Answers (2)

Johan
Johan

Reputation: 3611

The if statements has nothing to do with the time complexity - the operation of an if-statement has time complexity O(1), but the work in an if-statement can have a greater time complexity.

It's because list.get(i) is of O(n). To get the n:th element of a LinkedList you need to step n times in the list to find it. This is because a LinkedList doesn't save its indexes, only the first and last element in the list, and then its direct neighbours.

This is the time complexity for each of your functions:

public static int g(LinkedList<Integer> list) {
    int t = 0;

    for (int i = 0; i < list.size(); i++) {           // O(n) - loop
        int tgt = list.get(i);                        // O(n)

        for (int j = i + 1; j < list.size(); j++) {   // O(n) - loop
            if (list.get(j) == tgt)                   // O(n)
                t += list.get(j);                     // O(n)
        }
    }

    return t;
}

Since you're only iterating over 2 loops, it will initially make the time complexity O(n^2). The 3 calls of list.get(i) will make each make a time complexity of O(n), thus resulting in 3*O(n). This is however defaulted to O(n), and making the final time complexity to O(n) * O(n) * 3*O(n) => O(n^3)

Extra

On an unrelated note: You see that when you call list.get(j) twice, in the innermost loop, you will cause the program to iterate over the list twice, even though you just got the value.

if (list.get(j) == tgt)
    t += list.get(j);

Chances are that the processor or compiler will optimize this and save the value in the cache, but it's still a good idea to call list.get(j) once and store its value.

Upvotes: 3

Andy Turner
Andy Turner

Reputation: 140319

If statements are not loops.

Each get may take O(n), but the statements in its body are executed after the condition. So the if statement takes O(n)+O(n) (for the two gets), which is O(n).

That is nested inside two nested loops over a list of size n, so overall it is O(n^3).

Upvotes: 2

Related Questions