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

Solution: Big (O) of Nested Loop with Addition

Explore how to calculate the Big O time complexity of nested loops with addition by examining execution counts line by line. Understand the method to simplify expressions and identify the dominant term, equipping you to analyze algorithm efficiency confidently in coding interviews.

We'll cover the following...

Solution: #

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

On line 6 in the outer loop, int i=1; runs once, i<n; gets executed n3+1\frac{n}{3}+1 times and i+=3 executed n3\frac{n}{3} times. In the inner loop, int j=1; gets executed n3\frac{n}{3} times in total. j<n; executes n3×(n2+1)\frac{n}{3} \times (\frac{n}{2} +1) times and j+=2 gets executed n3×n2\frac{n}{3} \times \frac{n}{2} times. Study the following table for a more detailed line-by-line analysis of the calculation of time complexity.

Statement
Number of Executions
int n = 10;
1
int sum = 0;
1
float pie = 3.14;
1
int i=1;
11
...