while ( k<i && a[j] < a[k])
{
k++;
}
this while condition is checking the for the inversion in the array A.
if the array is sorted then there will be 0 inversions.
n = 5
i= 0
j = 0, j <i condition fails
i = 1;
j = 0; j < i, condition true
k<i; condition true, a[0] < a[0] condition false!
j=1; j<i, condition false.
i=2;
j=0; j< i, condition true
k<i, a[0] < a[0] condition false.
j=1, j< i, condition true
k<i, a[1] < a[0] // it's an inversion check, we assume that this condition is true.
k=1; k<i, a[1] < a[1] false.
j=2, j< i condition false.
i=3;
j=0; j<i, condition is ture
k was incremented to 1 in last iteration and it wasn't reset to 0.
k=1, k<i, && a[0] < a[1] condition false.
j=1, j<i,
k<i, a[1] < a[1] condition false.
j=2, j<i
k<i; a[2] < a[1] condition true, and K is incremented to 2
Conclusion,
if the array A is sorted then TC of while loop will be O(1) because a[j] < a[k] won't evaluate to true.
if Array A is sorted in reverse order, then while will run O(n) in total.
loop i and loop j are dependent, hence we will find total complexity of both loops.
that is O(n^2) as loop j will run 1+ 2 + 3 + 4 + ..... n-1
Time Complexity of this code is O(n^2)
