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