arraystime-complexityin-place

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


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.


Solution

  • We can see these patterns:

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