How to compare an element with other elements within an array efficiently for a condition

Question

I need to compare each index with one another and associated array value as well.

For example,

for(int i = 0; i < n - 1; i++) {

    for(int j = i + 1; j < n; j++) {

        if(a[i] > a[j]) { // Condition will be any 

            swap(a[i], a[j]); // Any action
        }
    }
}

Inside loops, there is a condition to check. Similarly I need to use any condition

eg: if(i + j == a[i] + a[j])

Could anyone help to optimize this index comparison? How to compare each index with other and element value with others efficiently i.e. less than O(n²)

Answer 1

In the general form you present, you have $\Theta(n^2)$ things to compare so you need $\Omega(n^2)$ time. If you know more about the arrays or the comparison operator (e.g., the arrays are sorted and the comparison is $<$ or $>$) then you can probably do something better but, without more restrictions, there's no hope.