...

/

Solution: Big (O) of Nested Loop with Multiplication

Solution: Big (O) of Nested Loop with Multiplication

This review provides a detailed analysis of the different ways to solve the Big (O) of nested loop with multiplication.

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(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)O(n). Have a look at the slides below for an in-depth explanation of the answer.

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

Access this course and 1400+ top-rated courses and projects.