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

Solution: Big O of Nested Loop with Multiplication

Explore the step-by-step process of determining the Big O time complexity for nested loops where the inner loop’s iterations grow exponentially. Understand how geometric series and logarithmic bounds influence the overall complexity, helping you evaluate and optimize Java code more effectively.

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

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