Big O complexity of loop with two independent inner loops

Question

I have a function that depends on three variables, T, N, and M. The loop is the following:

for each t from 0 to T {
    for each n from 0 to N {
         process(n,t);
    }
    for each m from 0 to M {
         process(m,t);
    }
}

What would be the big-O run-time complexity of this? I am thinking O(T*Max(n,m)) but is this standard? Thanks!

Answer 1

One way to analyze this is to look at the total amount of work being done across all iterations of the loop by determining how many times the outer loop executes and multiplying it by the amount of work done by the body of the loop. To do this, we'll work inside-out.

Starting with the inside, note that the first loop runs O(N) times, and does some amount of work on each iteration (I'll assume that it's O(1) work, though this analysis can be modified in case that's not true). Consequently, this loop does O(N) work. The second loop, similarly, does O(M) work. Thus the total amount of work done by the body of the loop is O(M + N). Since the top-level loop runs O(T) times, each iteration doing O(M + N) work, the total amount of work done is O(T(M + N)) = O(TM + TN).

Your claim that this is equal to O(T max{M, N}) is also correct. One way to see this is as follows: note that N = O(max{M, N}) and M = O(max{M, N}), and therefore we have that

O(TM + TN)

= O(T max{M, N} + T max{M, N})

= O(2T max{M, N})

= O(T max{M, N})

Hope this helps!