Data Structures for Coding Interviews in C++/

...

/

Solution: Nested Loop with Multiplication (Advanced)

Solution: Nested Loop with Multiplication (Advanced)

This review provides a detailed analysis of how to solve the Nested Loop with Multiplication challenge.

We'll cover the following...

Solution #

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

Solution Breakdown

In the main function, the outer loop is O(n)O(n) as it iterates n times. The inner while loop iterates i times, which is always less than n and the inner loop counter variable is doubled each time. Therefore we can say that it is O(log2(n))O(log_2(n)). Thus, the total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j which is less than i and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(i))O(log_2(\text{i})). But, the value of i at each iteration, of the outer loop, is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(i)⇒∑i=1nlog2(i)n \times log_2(i) \Rightarrow\sum_{i=1}^{n} log_2 (i)

⇒log2(1)+ ...