Search code examples
timebig-ocomplexity-theory

Time complexity of nested loop where the second loop iterates only for the last iteration of the above loop


Imagine a scenario where the second loop is iterated once for each iteration of n except the last one where it is iterated m times:

// n and m are two different variables.
for(int i=0; i<n; i++) {
  for(int j=0; j<m; j++) {
    if(i!=(n-1)) break;

    // O(1) code here.
  }
}

What would be the time complexity of this? Is it O(n*m), O(n+m) or something else?


Solution

  • EDIT: original answer was wrong based on a misread.

    This is O(n + m) because for n - 1 iterations of the outermost loop, a constant amount of work is done: it starts the inner loop and aborts on the first iteration. For the last iteration of the outermost loop, the innermost loop iterates m times, doing a constant amount of work each iteration. So, we have (n - 1) * x + 1 * (m * y) total steps, where x and y are some constants. And we know that (n - 1) * x + 1 * (m * y) = O(n + m) since we can drop the constant factors on our independent variables n and m.