AI Features
Home
Courses
Algorithms 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 a 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)) ...

Ask