CODEWITHSUNDEEP
algorithmtime-complexity
Ritik Sharma
Ritik Sharma

Reputation: 37

What will be the time complexity of this algorithm?

What will be the time complexity of the following code/algorithm? Shouldn't it be O(a^2)? My teacher said no and that I need to think harder and focus on the given constraints. Can anybody help me with this?

function(int a, int b)
{
    for(i=0; i<a; i++)
    {
        for(j=0; j<a-i; j++)
        {
            k = a-i-j;
            if(8*i+4*j+2*k == b)
                return;
        }
    }
}

Constraint:

Upvotes: 1

Views: 127

Answers (2)

Ma&#235;lan
Ma&#235;lan

Reputation: 4212

With the constraints given, assuming that you are interested in the worst-case complexity, it is still O(a²). Perhaps there is another constraint missing?

Paul’s answer is good and gives a precise account of the complexity. However, to find a worst-case complexity, you can just exhibit the worst case.

The equation 8i+4j+2k = b rewrites as 3i+j = b/2−a. Because j < a−i, the left-hand side is at most 3i+(a−i−1), in other words 2i+a−1. Because i < a, this is at most 2(a−1)+a−1, in other words 3a−3.

Take the largest possible b: b = 8a−2 (which satisfy both constraints: b is even and 2a < b < 8a). The right-hand side of the equation becomes (8a−2)/2−a, in other words 3a−1. This is strictly greater than 3a−3, therefore the equation has no solution. In this situation, the algorithm tries all (i,j), which is quadratic.

Upvotes: 1

Paul Hankin
Paul Hankin

Reputation: 58379

The code will stop early when it finds i, j such that 8i+4j+2(a-i-j)=b, that is 6i+2j=b-2a.

The j loop goes from 0 to a-i, so for j to be in range, have b-2a = 6i+2j < 6i+2(a-i) = 4i+2a, which gives 4i > b-4a.

So we'll need to execute (b-4a)/4 iterations of the i loop before we have a chance to find a j.

I'll skip the details, but it's possible to check for a>=6 there's always a j such that the loop exits when i is the first value that's at least (b-4a)/4 (given that b is even and 2a<b<8a).

Counting iterations (and counting the inner loop as always a iterations rather than a-i iterations, which will at worst give a factor of 2 error), we get a bound of a*max(1, b/4-a) iterations.

I've skimmed the details a lot here, but the result is that the complexity is Theta(a*max(1, b/4-a)).

Upvotes: 2

Related Questions