Search⌘ K
AI Features
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,⋯ ,n ...