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

Solution: Big (O) of Nested Loop with Multiplication

Understand how to analyze the time complexity of nested loops involving multiplication using logarithmic iterations and geometric series. Learn to derive the Big O notation of O(n) by examining loop execution patterns and their upper and lower bounds. This lesson equips you to evaluate nested loop complexities effectively in coding challenges.

We'll cover the following...

Given code

Java
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(log n)
			System.out.println("Pie: " + pie); // O(log n)
			
			for (int j = 0; j < var; j++) {  // 2n
				sum++;  //  (2n-1)
			}
			var *= 2; // O(log n)
		} //end of while loop
		
		System.out.println("Sum: " + sum); //O(1)
	} //end of main
} //end of class

Explanation

The answer is O(n)O(n). Have a look at the slides below for an in-depth explanation of the answer.

Time Complexity

The above slides give a detailed, step-by-step analysis of the code. Here, we provide a more summarized version.

The outer loop here runs log(n)log(n) times. In the first iteration of the outer loop, the body of the inner loop runs once. In the second iteration, it runs twice, and so on. The number of executions of the body of the inner loop increases in powers of 2. So, if kk is the number of iterations of the outer loop, the body of the inner loop runs a total of 1+2+4+8+⋯+2k1+2+4+8+\cdots+2^k times. This geometric series sums to 2k+1−12^{k+1}-1. The inner loop condition requires that in the last time the inner loop runs, it runs at most nn times. This requires 2k<n2^k < n ...