Question

What is the worst-case complexity of the each of the following code code fragments?

Two loops in a row:
for (i = 0; i < N; i++) {
sequence of statements
}
for (j = 0; j < M; j++) {
sequence of statements
}
How would the complexity change if the second loop went to N instead of M?

Answer 1

The worst-case time complexity of the given code fragments with two loops in a row can be determined by multiplying the number of iterations of each loop.

If the first loop has N iterations and the second loop has M iterations, the overall worst-case time complexity is O(N * M).

If the second loop were to go to N instead of M, the worst-case time complexity would be O(N²) because both loops would have N iterations, and their iterations would be nested. In big O notation, nested loops result in the product of their iterations. The worst-case time complexity of the given code fragments with two loops in a row can be determined by multiplying the number of iterations of each loop.