0
$\begingroup$

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²)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.