Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Solution: Big O of a Nested Loop with Addition

Understand how to break down nested loops to measure their time complexity. This lesson guides you through analyzing each loop component and calculating the overall Big O complexity, helping you improve your algorithm evaluation skills.

We'll cover the following...

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 1 unit of time. The comparison (var < n) gets executed ...