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

Solution: Nested Loop with Multiplication (Pro)

Explore how nested loops with a multiplication factor affect time complexity by analyzing each statement's execution count. Understand how the inner loop's logarithmic iteration leads to an overall linear O(n) complexity. This lesson helps you evaluate algorithm efficiency by breaking down loop behavior in C++ code.

We'll cover the following...

Solution

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

The outer loop in the main function has n iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to 1 in the code since the j is immediately doubled, therefore inner while loop will run O ...