Time complexity for the following algorithm

Question

What is the time complexity of the following algorithm, how can I find the best and worst case in my code:

boolean b = true;
integer rn = 0;
for(int i=1; i<=n; i++)
{
    for(int j=1; j<=m; j++)
    {
        rn = Math.Random() // random number between j and m 
        if(j%rn==0) b = false;
        while(b)
        {
            for(int k=1; k<=o; k++)
            {
                for(int l=1; l<=p; l++)
                {
                    //some stuff
                    rn = Math.Random() // random number between l and p
                    if(l%rn==0) b=false;
                }
            }
        }
        b = true;
    }
}

The first two for loops will always run so I guess this is the best case but how can I measure the worst case here?

You are using a breaking condition which depends on Random Function. In worst case, You may end up getting stuck in an infinite loop if b never becomes false. — Sanket Makani
– Sanket Makani, Commented Mar 15, 2018 at 14:37
@SaiBot No they are all different for all for loops. So n is not equal to m an not equal to o and not equal to p — J. Doe
– J. Doe, Commented Mar 15, 2018 at 14:37
@J.Doe how can m be different in all loops, it is never set to anything? — SaiBot
– SaiBot, Commented Mar 15, 2018 at 14:38

meowgoesthedog · Accepted Answer · 2018-03-15 15:31:56Z

Assuming that rn is in [j, m] inclusive, there are m - j + 1 numbers in this range; using basic modulo logic there are floor((m - j + 1) / j) of them which satisfy the if condition. Adopting a probabilistic approach and assuming that Random() is uniform, the total time complexity is given by:

Where P(m,j) is the probability of the if condition being satisfied - i.e. of the while-loop not executing, and S(o,p) is the time complexity of the while-loop. Since the inner loops are independent of i, j, we can treat them separately.

While it initially looks like the inner loops will require a similar analysis, there are two key differences to note:

b is never reset to true until after the while loop.
The if condition does not cause any of the loops to break.
But most importantly, b will always be false by the time the two for-loops break. Why? because when l = p, the only possible value for rn to take is also p; p % p = 0 so b will always be set to false if it hadn't already.

Therefore the inner while loop only executes up to once, and S(o,p) = O(op) trivially. Combining the two results, we get:

Summing over the 1 trivially gives O(mnop), but what about the P(m,j)? Using the fact that a number rounded down differs from its original value by less than 1:

Where in step (1) we did an index shifting transformation, and in step (2) used the asymptotic Harmonic series summation. Since this logarithmic term from the probabilistic analysis is overshadowed by the "bulk" term from before:

O(mnop) is therefore both the average and worst case complexity.

OmG · Accepted Answer · 2018-03-15 15:34:13Z

1

As you have random variables in your code, it would be rational to compute expected values of time complexity. Two outer loop runs in m*n. The condition of inner while is true ifj%rn == false. As, rn is between j to m, and greater than j, hence the condition will be true if rn == j, so the chance of entering to the while loop is 1-1/(m-j+1). Therefore, the expected running time of the algorithm would be m*n( sum of 1/(m-j+1) + (m-j)/(m-j+1) * (time complexity of inner of while loo) from j = 1 to m).

To complete the case, we should time complexity of inner while. Two loops compute in o*p. The iteration of running these two loops depends on the successful condition of b = false. As, finally l would be equal p, in running these two loops l%rn would be equal zero. Because rn is between l and p, and if l would be equal p, the probability of l%rn == 0 would be 1. Hence, these two loops running in o*p.

In sum, time complexity of the algorithm would be m*n( sum of 1/(m-j+1) * 1+ (m-j)/(m-j+1) * (o*p) from j = 1 to m) which is O(m*n(log m + (m-log m)*o*p))=O(m^2*n*o*p)

answered Mar 15, 2018 at 15:34

OmG

19k13 gold badges69 silver badges96 bronze badges

1 Comment

meowgoesthedog Over a year ago

Where does the second factor of m come from?

Collectives™ on Stack Overflow

Time complexity for the following algorithm

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related