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

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,⋯ ,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 that a cinner loop has log3(n)log_3(n) iterations. ...

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}