Data Structures for Coding Interviews in Java/

...

/

Solution: Big O of a Nested Loop with Subtraction

Solution: Big O of a Nested Loop with Subtraction

This review provides a detailed analysis of the different ways to solve the Nested Loop with Subtraction challenge.

We'll cover the following...

Given Code #

Press + to interact
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) ...