Search⌘ K
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(log2(n))O(log_2(n)) times for all the iterations of the outer loop.

Note: Inner while loop will run at most once for each iteration of the outer loop.

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
float pie = 3.14;
1
int i=0;
11
i<n;
n+1n+1
i++
...