...

/

Solution: Big (O) of a Nested Loop with Addition

Solution: Big (O) of a Nested Loop with Addition

This review provides a detailed analysis of the time complexity of the nested loop with addition problem!

Given code

Press + to interact
class NestedLoop {
public static void main(String[] args) {
int n = 10; // 1 step --> Note: n can be anything. This is just an example
int sum = 0; // 1 step
double pie = 3.14; // 1 step
for (int var = 0; var < n; var = var + 3) { // n/3 steps
System.out.println("Pie: " + pie); // n/3 steps
for (int j = 0; j < n; j = j + 2) { // (n/3 * n/2) steps
sum++; // (n/3 * n/2) steps
System.out.println("Sum = " + sum); // (n/3 * n/2) steps
}
}
}
}

Solution breakdown

The first for loop on line 7 can be broken down into 3 parts:

  • initialization
  • comparison
  • incrementation

Since the initialization (int var = 0) only happens once in the entire program, it takes one unit of time. The comparison (var < n) gets executed (n3+1)(\frac{n}{3} + 1) times and the increment runs n3\frac{n}{3} ...

Access this course and 1400+ top-rated courses and projects.