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) times since var will first be equal to 11, then 33, then 9,⋯9,\cdots, until it is 3k3^k such that 3k<n3^k < n. In the inner loop, int j=1; runs log3(n)log_3(n) times, j<n gets executed log3(n)×(n2+1)log_3(n)\times(\frac{n}{2}+1) times and j+=2 executed log3(n)×n2log_3(n)\times\frac{n}{2} times. The sum+=1; line also runs a total of log3(n)×n2log_3(n)\times\frac{n}{2} ...