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

Solution: Nested Loop with Multiplication (Intermediate)

Explore how to analyze the time complexity of nested loops where the outer loop increments by a constant and the inner loop multiplies, leading to log-based iterations. Learn how to express running time using Big O notation, focusing on the derivation of O(n log n) complexity relevant to algorithm optimization.

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 cinner 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;