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

Solution: Nested Loop with Multiplication (Basic)

Explore how to analyze the time complexity of a nested loop involving multiplication. Learn to break down the outer loop running logarithmically and the inner loop iterating linearly, culminating in identifying the overall Big O complexity as O(n log n). This lesson equips you with skills to evaluate algorithms’ efficiency in interview 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(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) ...