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

Solution: Nested Loop with Multiplication (Intermediate)

Understand how to analyze nested loops where the outer loop increments linearly and the inner loop multiplies. Learn to calculate the time complexity, focusing on logarithmic growth and deriving the Big O notation for efficient algorithm evaluation.

We'll cover the following...

Solution #

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

  • The outer loop index i goes: 1,4,7,10,⋯ ,n1,4,7,10,\cdots,n. That means that the outer loop has n3\frac{n}{3} iterations

  • The inner loop index j goes: 1,3,9,27,⋯ ,n1,3,9,27,\cdots,n. That means that a complete run of the inner loop has log3(n)log_3(n) iterations. ...

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
float pie = 3.14;
1
int i=1;
11
i<n;
n3+1\frac{n}{3}+1
i+=3
n3\frac{n}{3}
cout << pie << endl;