Search⌘ K
AI Features

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

Explore how to break down and calculate the running time of nested loops using Big O notation. This lesson explains each loop component, counts executions, and guides you through deriving the overall time complexity, helping you develop a strong foundation in asymptotic analysis for coding interviews.

Given code

Java
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 ...