Search⌘ K
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) times since var will first be equal to 11, then 33, then 99, then 27,⋯27,\cdots, until it is 3k3^k such that 3k<n3^k < n. This means that the outer loop runs a total of log3(n)log_3(n) times.

Now, let’s have a look at the inner loop for(int j = 1; j < n; j += 2). int j = 1; runs log3log_3 times, j<n executed log3(n)×n2+1log_3(n)\times\frac{n}{2}+1 times and j += 2 executed 2(log3(n)×n2)2(log_3(n)\times\frac{n}{2}) times. sum++; also runs a total of ...