AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Solution: Nested Loop with Multiplication (Advanced)

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