Algorithms for Coding Interviews in Java/

...

/

Solution: Nested Loop with Multiplication (Basic)

Solution: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of how to solve the nested loop with a multiplication problem.

We'll cover the following...

Given code

Press + to interact
class NestedLoop {
	public static void main(String[] args) { 
		int n = 10; // O(time complexity of the called function)
		int sum = 0; //O(1)
		double pie = 3.14; //O(1)
		int var = 1;
			
		
		while(var < n) { // O(log3 n)
			System.out.println("Pie: " + pie); // O(log3 n)
		
			for (int j = 1; j < n; j = j + 2) {  // O((log3 n)* (n/2)) 
				sum++;  // O((log3 n)* (n/2) * 2) 
			}
			var *= 3;  // O(log3 n)
		} //end of while loop
		System.out.println("Sum: " + sum); //O(1)
	} //end of main
} //end of class

Time complexity

The outer loop in this problem, i.e., everything under line 9 while (var < n) runs log3(n)log_3(n) times since var will first be equal to 11, then 33, then 66, then ...

Access this course and 1400+ top-rated courses and projects.