Doubt in this question


#1
        int j = 0;
        for(int i = 0; i < n; ++i) {
            while(j < n && arr[i] < arr[j]) {
                j++;
            }
        }

still not convinced by the solution as it is nested loop so inner while loop will run atmost n times and outer loop also runs for n times so overall complexity should be O(n*n).


#2

Inner loop runs N times but only once(for i=0),because after that j becomes N and remains N .so inner loop will not run for i>=1.


#3

what about if array is random?


#4

Array has constant size (N), no matter if values are random.


#5

The inner loop will only execute n times when i = 0 and all elements are greater than arr[0].
After this iteration, j = n, thus this inner loop will never be entered for the rest of i’s.
Thus, we have O(n) for the first iteration and every other iteration are simply checking the conditions of the while loop (that will never be executed) which will be done for i = 1,2, … , n - 1 => n - 1 times, thus we get O(N) + O(N - 1) => O(N) + O(N) => 2O(N) as described in the solution