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

Solution: Big (O) of Nested Loop with Multiplication

Explore how to analyze the time complexity of a nested loop where the inner loop iterations multiply in powers of two. Understand how to apply Big O notation with logarithmic bounds and geometric series to determine an upper time complexity bound of O(n). This lesson helps you grasp key concepts for algorithm analysis and complexity measures.

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 ...