Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Big (O) of Nested Loop with Subtraction

Explore how to calculate the time complexity of nested loops that decrement by subtraction. Learn to analyze individual statement executions, combine them, and derive the overall big O notation for algorithm efficiency.

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