Algorithms for Coding Interviews in Java/

...

/

Example: Time Complexity of an Algorithm With Nested Loops

Example: Time Complexity of an Algorithm With Nested Loops

In this lesson, you will learn how to compute the time complexity of an algorithm that involves nested for loops.

We'll cover the following...

Now, we’ll analyze an algorithm with nested for loops.

A program with nested for loops

Consider the following Java program:

Press + to interact
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 6. From the previous lesson, you will recall that it accounts for 6n+46n + 4 ...

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