Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

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

Learn to break down nested loop executions involving subtraction to calculate time complexity. This lesson guides you through analyzing each loop iteration and simplifying the results to determine the Big O notation, enhancing your algorithm analysis skills.

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