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

Solution: Nested Loop with Multiplication (Basic)

Explore how to calculate the time complexity of a nested loop involving multiplication using log base 3 and n factors. Understand breaking down each line's execution count, simplifying to Big O notation, and converting log bases for clarity in complexity analysis.

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