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

Solution: Nested Loop with Multiplication (Intermediate)

Explore the time complexity analysis of nested loops with multiplicative inner loops in C++. Learn to calculate iteration counts, apply logarithmic base changes, and derive Big O notation resulting in O(n log n) time complexity.

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,⋯ ,n ...