...

/

Solution: Nested Loop with Multiplication (Basic)

Solution: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of how to solve the nested loop with a multiplication problem.

We'll cover the following...

Given Code #

Press + to interact
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 ...