Data Structures for Coding Interviews in Java/

...

/

Solution: Nested Loop with Multiplication (Pro)

Solution: Nested Loop with Multiplication (Pro)

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

We'll cover the following...

Given Code #

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

The outer loop has n iterations as it iterates on var from 0 to n-1. If the condition j < var is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to 1 in the code. The inner while loop will run at most once for each iteration of the outer loop. Therefore, lines 12 and 13 run O(n)O(n) times, each. Since we are interested in an upper bound on the worst-case running time, let’s assume these statements run exactly n times.

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
double pie = 3.14;
1
int var=0;
11
var<n;
n+1n+1
...