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

Example: Time Complexity of an Algorithm With Nested Loops

Understand how to analyze the time complexity of algorithms with nested loops in Java. Explore the step-by-step calculation of primitive operations and see how nested iterations affect overall performance.

We'll cover the following...

A Program With Nested for Loops

Consider the following Java program:

Java
class NestedLoop {
  public static void main(String[] args) {
    int n = 5; // 1 step
    int m = 7; // 1 step
    int sum = 0; // 1 step
    for (int i = 0; i < n; i++) { // n steps
      for (int j = 0; j < m; j++) { // n*m steps
        sum++; // n*m steps
      }
    }
    System.out.println("Sum: " + sum); // 1 step
  } 
}

It is a simple piece of code that prints the number of times the increment statement runs throughout the program. Let’s compute its time complexity.

Time Complexity

Let’s take the training wheels off and jump straight to line number 6 which accounts for 6n+46n + 4 primitive operations: one for initialization, 3×(n+1)3\times(n + 1) for the comparison, and 3×n3\times n for the increment.

Let’s move onto line number 7. Since this line is nested inside the for loop on line 6, it is repeated nn times. For a single iteration of the outer for loop, how many primitive operations does this line incur? The answer is 6m+46m + 4 ...