How should I calculate the Time complexity for the below code?

Question

The below solution is to calculate the in-place frequency count of the numbers present in the array

int arr[] = {4, 5, 6, 8, 1, 2, 3 , 4, 1, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);

cout << "size: " << size << "\n";

for(int i = 0; i < size;) {
    if(arr[i] > size) {
        arr[i] = 0;
        i++;
    }
    if(arr[i] <= 0) {
        i++;
        continue;
    }
    int indexToUpdate = arr[i] - 1;
    if(arr[indexToUpdate] < 0) {
        arr[i] = 0;
        arr[indexToUpdate]--;
        i++;
    } else {
        arr[i] = arr[indexToUpdate];
        arr[indexToUpdate] = -1;
    }
}
for(int i = 0; i < size; i++) {
    cout << i << " : " << arr[i] << "\n";
}

the time complexity for the solution.

Answer 1

We can see these patterns:

• Once an array value gets a negative value, it will never become positive again:

  • arr[i] = 0; and arr[i] = arr[indexToUpdate]; can only execute when arr[i] was strictly positive, and they don't make arr[i] negative.
  • arr[indexToUpdate]-- decreases a value that was already negative
  • arr[indexToUpdate] = -1 is the only remaining modification of an array element, and it is the only one that changes its sign. And that change is from non-negative to negative
  • There is no case where a negative value is updated to a non-negative value

• One iteration of the loop will either increase i, or turn a non-negative value into a negative value.

  • Increasing i can only happen size times, as then the loop exits
  • Making a non-negative value negative, can only happen size times, as then all values will be negative

Conclusion: the loop can make 2*size iterations at the most. So this is O(n).