Worse case scenario should be counted


#1

How we can assume that the array is in decreasing order when time complexity is calculated for the worst case scenario?
We should count for all the iterations.
For increasing array values, the while loop also will be O(n), and since it is inside the for loop, it the O should be O(n*n).


#2

Even if we take the array in increasing order, then in the first iteration, j will be equal to n, then as j is not initialised again to 0, the condition j < n will always be false, hence making the complexity O(n+1) , that is why the worst case comes when the array is in decreasing order


#3

Decreasing order :

int arr[4] = {4,3,2,1};
int j = 0,c=0, n=4;
for(int i = 0; i < n; ++i) {
while(j < n && arr[i] < arr[j]) {
j++;
printf("%d\n",++c);
}
}

Executes : 3 times
j=0<4, 4<4
j=1<4, 4<3(prints)
j=2<4, 4<2(prints)
j=3<4, 4<1(prints)
j=4<4 fails from here.

O(n-1)

Increasing order :

int arr[4] = {1,2,3,4};
int j = 0,c=0, n=4;
for(int i = 0; i < n; ++i) {
while(j < n && arr[i] < arr[j]) {
j++;
printf("%d\n",++c);
}
}

Executes : 0 times