Great complexity loops with two independent inner loops

Question

I have a function that depends on three variables: T , N and M The cycle is as follows:

 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 difficulty of this time? I think O(T*Max(n,m)) , but is this the standard? Thanks!

Answer 1

One way to analyze this is to look at the total amount of work performed on all iterations of the cycle, by determining how many times the external cycle performs and multiplies it by the amount of work performed by the body of the cycle. To do this, we will work inside out.

Starting from the inside, note that the first loop starts O (N) times and does some work at each iteration (I will assume that it works O (1), although this analysis can be changed if this is not so). Therefore, this loop runs O (N). Similarly, the second loop runs O (M). Thus, the total amount of work performed by the body of the cycle is O (M + N). Since the top-level loop runs O (T) times, each iteration that runs O (M + N) works, the total amount of work done is O (T (M + N)) = O (TM + TN).

Your statement that this is 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!

Answer 2

Yes this is correct. And this is the same as O(T*(m+n)) . What is “standard” is hard to say, but max seems to be used more often.