Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Solution: Nested Loop with Multiplication (Intermediate)

Understand how to calculate the time complexity of nested loops where both loops increment multiplicatively. Explore the step-by-step breakdown of iterations and derive the Big O notation, including handling logarithmic terms and base transformations for efficient Java code analysis.

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,⋯ ,n1,3,6,9,\cdots,n. That means that the outer loop has n3\frac{n}{3} iterations.

  • The inner loop index j goes: 1,3,9,27,⋯ ,n1,3,9,27,\cdots,n. That means the inner loop has about log3(n)log_3(n) iterations per outer loop iteration (as j is reset to 1 after each run). ...

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
double pie = 3.14;
1
int var=1;
11
var<n;
n3+1\frac{n}{3}+1
var+=3
n3\frac{n}{3}