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

Solution: Big O of a Nested Loop with Subtraction

Explore how to analyze the time complexity of nested loops where the outer loop decrements by 3 and the inner loop counts down linearly. This lesson breaks down execution counts per statement, leading to a clear calculation of the quadratic time complexity O(n²). Gain insight into evaluating algorithm performance with nested loops in Java.

We'll cover the following...

Given Code #

Java
class NestedLoop {
  public static void main(String[] args) {
    int n = 10; // O(time complexity of the called function)
    int sum = 0; //O(1)
    double pie = 3.14; //O(1)
    
    
    for (int var = n; var >= 1; var = var - 3) { // O(n/3)
      System.out.println("Pie: " + pie); // O(n/3)
      
      for (int j = n; j >= 0; j = j - 1) { // O((n/3)*(n+1))
        sum++; // O((n/3)*(n+1))
      }
    } //end of outer for loop
  System.out.println("Sum: " + sum);//O(1)
  } //end of main
} //end of class

Solution Breakdown

On line 8 in the outer loop, int var=n; runs once, var>=1; gets executed n3+1\frac{n}{3}+1 times and var-=3 executed n3\frac{n}{3} times. In the inner loop, int j=n; gets executed n3\frac{n}{3} times in total, j>=0; executes n3× (n+2)\frac{n}{3} \times \ (n+2) times and j=j-1 gets executed n3× (n+1)\frac{n}{3} \times \ (n+1) ...