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

Solution: Big (O) of Nested Loop with Multiplication

Explore how to analyze the time complexity of nested loops where the inner loop runs in powers of two relative to the outer loop. Learn to use geometric series and logarithmic bounds to establish the Big O notation for this algorithmic pattern.

We'll cover the following...

Solution

C++
int main() {
  int n = 10;    
  int sum = 0;   
  float pie = 3.14;  
  int var = 1;
  while (var < n){      // O(log n)
    cout << pie << endl; // O(log n)
    for (int j=0; j<var; j++)  // 8n - 12
      sum+=1;    //  (4n-6)
    var*=2;  // O(log n)
  }
  cout<<sum; 
}

Time Complexity

The outer loop here runs log(n ...