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

Solution: Nested Loop with Multiplication (Pro)

Explore how to determine the time complexity of a nested loop where the inner loop doubles its iterator. Understand the use of logarithmic analysis and how to simplify expressions to Big O notation to evaluate algorithm efficiency.

We'll cover the following...

Solution

C++
int main(){
  int n =10;    // you can change the value of n
  int sum = 0;
  int j = 1;
  float pie = 3.14;
  
  for (int i = 0; i < n; i++){
    cout << pie << endl;
    while (j < i){
      sum+=1;
      j*=2;  
    }
  }
  cout << sum << endl;
}

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