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

Solution: Nested Loop with Multiplication (Advanced)

Explore how to break down the time complexity of nested loops where the inner loop doubles each iteration. Understand how this results in a combined complexity of O(n log n) by analyzing the logarithmic growth and factorial relationships involved.

We'll cover the following...

Solution

C++
int main(){
  int n =10;   //O(1)   
  int sum = 0; //O(1)   
  float pie = 3.14; //O(1)   
  
  for (int i = 0; i < n; i++){ //O(n)
    int j = 1; //O(n)
    cout << pie << endl; //O(n)
    while (j < i){ // O((n) * (log2 var))
      sum+=1; // O((n) * (log2 var))
      j*=2;  // O((n) * (log2 var))
    }
  }
  cout << sum << endl; //O(1)   
}

Solution Breakdown

In the main function, the outer loop is O(n)O(n) ...