Complexity including randomness

Question

I have the following three loops:

for i in range(m)
    for j in range(n)
        r = random(0,l)
        for k in range(r)
            
        l = l-r

and I am wondering what the complexity is here, does the last one equate to O(1)? The first two loops should be O(m*n). l,m,n are of course integers.

Answer 1

The original value of 𝑙 sets a maximum to the total number of times the inner loop can make an iteration. Put in another way, the sum of all values that 𝑟 will get, cannot exceed the original value of 𝑙.

So for the outer two loops we have θ(𝑛𝑚), and add to that the worst case for the total number of iterations of the inner loop, and we get a worst case time complexity of O(𝑛𝑚+𝑙).

NB: the best case occurs when random always returns 0. In that case we get θ(𝑛𝑚) as time complexity.