Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Solution: Nested Loop with Multiplication (Pro)

Explore how nested loops with a multiplying inner loop affect the time complexity of an algorithm. Understand the step-by-step execution counts and learn to derive the Big O notation as O(n) from the given Java code example.

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
...