Data Structures for Coding Interviews in C++/

...

/

Example: Time Complexity of an Algorithm With Nested Loops

Example: Time Complexity of an Algorithm With Nested Loops

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

We'll cover the following...

In the previous lesson, we learned how to calculate the time complexity of an algorithm that involves a loop. Now, we’ll extend the same idea to analyzing an algorithm with nested for loops.

A Program With Nested for Loops #

Consider the following C++ program:

Press + to interact
int main(){
  int n = 5;
  int m = 7;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++)
      sum += 1;
  }
  cout << sum;
  return 0;
}

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 5. From the previous lesson, you would recall that it 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 6. Since this line is nested inside the for loop on line 5, it is repeated nn times. For a single iteration of the outer for loop, how many primitive operations does this line incur? You should be able to generalize from the last lesson that the answer is ...