Algorithms for Coding Interviews in Java/

...

/

Solution: Nested Loop with Multiplication (Advanced)

Solution: Nested Loop with Multiplication (Advanced)

This review provides a detailed analysis of the different ways to solve the nested loop with a multiplication challenge.

We'll cover the following...

Given code

Press + to interact
class NestedLoop {
	public static void main(String[] args) {
    int n = 10; //O(1)   
		int sum = 0; //O(1)
		double pie = 3.14; //O(1)
		for (int var = 0; var < n; var++) {    //O(n)
      int j = 1;  //O(n)
			System.out.println("Pie: " + pie); //O(n)
			while(j < var) { // O((n) * (log2 var))
        sum += 1; // O((n) * (log2 var))  
        j *= 2;  // O((n) * (log2 var))
      }
    } //end of for loop
    System.out.println("Sum: " + sum); //O(1)
  } //end of main
} //end of class

Solution breakdown

In the main function, the outer loop is O(n)O(n), as it iterates n times. The inner while loop iterates var 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)). Therefore, 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 var and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(var))O(log_2(\text{var})). However, the value of var 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(var)⇒∑var=1nlog2(var)n \times log_2(var) \Rightarrow\sum_{var=1}^{n} log_2 (var) ...