Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Nested Loop with Multiplication (Pro)

Explore the step-by-step analysis of nested loops with multiplication to evaluate time complexity. This lesson helps you understand how to identify runtime upper bounds, apply logarithmic and linear terms, and derive the Big O notation for efficient algorithm assessment.

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, j is immediately doubled. Note that j is not reset to 1 in the code. The inner while loop runs 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
var++
...