Search⌘ K
AI Features

Solution: Nested Loop with Multiplication (Intermediate)

Explore how to analyze the time complexity of a nested loop where the outer loop increments by addition and the inner loop increments exponentially. Understand how to compute the number of executions and derive the Big O notation, focusing on how logarithmic and linear terms contribute to overall performance.

We'll cover the following...

Given code

Java
class NestedLoop {
public static void main(String[] args) {
int n = 10;
int sum = 0;
int j = 1;
double pie = 3.14;
for (int var = 1; var < n; var += 3) { // O(n/3)
System.out.println("Pie: " + pie); // O(n/3)
j = 1; // O(n/3)
while (j < n) { // O((n/3) * (log3 n))
sum += 1; // O((n/3) * (log3 n))
j *= 3; // O((n/3) * (log3 n))
}
}
System.out.println("Sum: " + sum); //O(1)
}
}
  • The outer loop index i goes: 1,3,6,9,,n ...