Hi, im struggling to understand O-notation runtime for the if statement in this piece of code

Question

for (int i=0; i<V-1; i++) {
    for (int j=i+1; j<V; j++) {
        if (matrix[i][j]) {
            from[nextedge]=i;
            to[nextedge]=j;
            nextedge++;
        }
    }
}

I am trying to find out the o notation runtime for the if statement and inner for loop but am struggling with how to solve this

Answer 1

This entire code is O(V^2) because the sum of x from x=1 to x=V is (1/2)V(V+1). The inner loop is O(V) because the maximum number of iterations it must complete is V-1 The if statement is O(1): there is a constant maximum of steps it completes.

Answer 2

You have two nested for loops, each of which depends on the size of V. So your total complexity would be O(V²).

Answer 3

The loop for(int i = 0; i < V - 1; i++){} would be O(n) by itself.

You then run for (int j=i+1; j<V; j++) {} inside this loop. Each iteration of i this loop runs one less time. This is V + V-1 + V-2...2+1. This is V/2. This results in V * V/2 or V * 0.5 V. Since 0.5 is a constant it is not used, resulting in V * V or O(V²)

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#application See "Nested loops", item 4.

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html