Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C++

Solution: Big (O) of Nested Loop with Subtraction

Understand how to calculate the time complexity of nested loops where the outer loop decreases by a step and the inner loop iterates fully. This lesson guides you through step-by-step analysis and identifies the dominant Big O complexity as O(n squared).

We'll cover the following...

Solution #

C++
int main(){
  int n = 10;  
  int sum = 0;  
  float pie = 3.14;    
  for (int i=n; i>=1; i-=3){   // O(n/3)
    cout << pie << endl;    // O(n/3)
    for (int j=n; j>=0; j--){     // O((n/3)*(n+1))
      sum += 1;   // O((n/3)*(n+1))
    }
  }
  cout << sum << endl;    
}

On line 6 in the outer loop, int i=n; runs once, i>=1; gets executed n3+1\frac{n}{3}+1 times and i-=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-- gets executed n3× (n+1)\frac{n}{3} \times \ (n+1) ...