Question

1. Let A = ha1, a2, . . . , ani be an array of numbers. Let’s define a ’flip’ as a pair of distinct indices i, j ∈ {1, 2, . . . , n} such that i < j but ai > aj . That is, ai and aj are out of order. For example - In the array A = [1, 3, 5, 2, 4, 6], (3, 2), (5, 2) and (5, 4) are the only flips i.e. the total number of flips is 3. (Note that in this example the indices are the same as the actual values)

At most, how many flips can A contain in terms of the array size n?

Answer 1

If the array is sorted in reverse order like: [6, 5, 4, 3, 2, 1], then there will total 5 + 4 + 3 + 2 + 1 = 15 inversions (flips)

So, for an array of size N, It will be: 1 + 2 + .. + (N-1) = N(N-1)/2 flips

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.