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

Solution: Nested Loop with Multiplication (Basic)

Explore how to compute the time complexity of nested loops involving multiplication in C++. Learn to use logarithmic analysis and Big O notation to understand algorithm efficiency, preparing you for coding interview challenges.

We'll cover the following...

Solution

The code for this challenge is reproduced below:

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

Time Complexity

The outer loop in this problem runs log3(n)log_3(n) ...