Data Structures for Coding Interviews in C++/

...

/

Solution: Big (O) of Nested Loop with Addition

Solution: Big (O) of Nested Loop with Addition

This review provides a detailed analysis of the time complexity of the Nested Loop with Addition problem.

We'll cover the following...

Solution: #

C++
int main(){
  int n = 10;
  int sum = 0;     
  float pie = 3.14;   
  for (int i=0; i<n; i+=3){  // O(n/3)
    cout << pie << endl;        // O(n/3)
    for (int j=0; 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=0; 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=0; 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. See 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=0;
11
i<n;
n3+1\frac{n}{3}+
...