How to compute time complexity of an infinite loop which is sure to end at a point?

Question

So I have the following code, for which first I was using a while(true) with breaking it using an if statement with the same condition which is now in my do-while loop.

The code now looks like this:

do {
        for (int i = 0; i < arrayToUse.length; i++) {
            int diff = arrayToUse[i] - number;

            if (diff >= 5) {
                arrayToUse[i] -= 5;
                count++;
                break;
            }

            if (diff >= 2) {
                arrayToUse[i] -= 2;
                count++;
                break;
            }

            if (diff == 1) {
                arrayToUse[i] -= 1;
                count++;
                break;
            }
        }

        if(preCount == count)
            break;

        preCount = count;

    } while (!allElementsEqual(arrayToUse, number));

Here arrayToUse is the array I receive as the input. And the code for allElementsEqual() looks like this:

static boolean allElementsEqual(int[] arr, int num){

    for(int i=0;i<arr.length;i++){
        if(arr[i] != num)
            return false;
    }

    return true;
}

I have timeouts in the code I am using this for, and I am not able to find how can I compute the time complexity of an algorithm that has not really well defined time of end. I am talking about time complexity in Big Oh Notation.

I would appreciate any help.

Answer 1

Current Complexity:

Let´s call m the maximum number of the array. Your first loop will run at most N times to find a number that is still greater than num. When it does, it brings it closer to num in at most 5 units. The 2 and 1 unit is not important for the complexity, but the important part is that it will always bring it closer to num.

So when you have changed an element, you break the loop to find the number and then won´t break the do while because the precount will be different than count. Then the allElementsEqual function runs and that is also O(n). So for each run of the do while, you do twice O(n) operations. What remains is how many times can this do while loop run.

It can only stop when all elements are equal, and we said that in each step we bring 1 number closer to num by at most 5. This will mean that for each number in our array, it will run about ((originalNumber[i] - num) / 5) times, and the worst case is on the maximum which was m. So it will take about (m - num) / 5 loops to bring only that number equal to num. If all numbers were the maximum, this would mean that for each number we will do (m - num) / 5 steps to equal it to num.

This gives us (m - num) / 5 steps for each number, there are N numbers and each step costs O(n), all in all giving a complexity of O((m - num) / 5 * N * N). We can remove the /5 and just leave it as O((m - num) * N * N).

As a side note, using while(true) instead of allElementsEqual is the same, because your precount == count if is already taking care of checking that.

Can we do better?

Assuming we remove the allElementsEqual for true, that changes the operation to O(1) instead of O(n) but we still have the loop to find the number not equal to num that is O(n). If we change the i to be initialized at 0 outside the do while so that it does not start at 0 on every step, it will change the operation to O(1) and still work, because the breaks will prevent i from updating until the difference is 0 and when the difference is 0 we don´t care anymore about that number so we can increase i. This changes the algorithm to O((m - n) * N)

Can we do even better?

Instead of bringing the number closer to num with at most 5 units, why don´t we do it all at once? We can count the number of times we will need to reduce it by 5, the times we will reduce by 2 (0, 1 or 2 times) and the times by 1 (0 or 1 time).

int diff = arrayToUse[i] - number;

count += floor(diff / 5) + floor((diff % 5) / 2) + (diff % 5) % 2
arrayToUse[i] = number;

With this, we can do it in O(N) and can´t be done better as we need to read each number. So this is optimal