Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Nested Loop with Multiplication (Advanced)

Explore how to break down nested loop code involving multiplication to determine its time complexity. Understand the use of logarithmic analysis and factorial log properties to simplify complexity expressions. This lesson helps you master asymptotic analysis for nested loops critical in coding interviews.

We'll cover the following...

Given code

Java
class NestedLoop {
	public static void main(String[] args) {
    int n = 10; //O(1)   
		int sum = 0; //O(1)
		double pie = 3.14; //O(1)
		for (int var = 0; var < n; var++) {    //O(n)
      int j = 1;  //O(n)
			System.out.println("Pie: " + pie); //O(n)
			while(j < var) { // O((n) * (log2 var))
        sum += 1; // O((n) * (log2 var))  
        j *= 2;  // O((n) * (log2 var))
      }
    } //end of for loop
    System.out.println("Sum: " + sum); //O(1)
  } //end of main
} //end of class

Solution breakdown

In the main function, the outer loop is O(n)O(n), as it iterates n times. The inner while loop iterates var times, which is always less than n, and the inner loop counter variable is doubled each time. Therefore, we can say that it is O(log2(n))O(log_2(n)). Therefore, the total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j, which is less than var and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(var))O(log_2(\text{var})). However, the value of var at each iteration of the outer loop is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(var)⇒∑var=1nlog2(var)n \times log_2(var) \Rightarrow\sum_{var=1}^{n} log_2 (var) ...