Problem 8. (10 points) Find the number of inversions in the following array without applying brute...

  

Transcribed Image Text:

Problem 8. (10 points) Find the number of inversions in the following array without applying brute force. You may want to note that the first 10 items are sorted in reverse order and the last 10 items are sorted in order. Show enough work or explanation to see that you aren't using an O(n²) brute force algorithm. 81 77 73 69 66 62 52 41 36 23 12 31 33 57 61 68 75 76 78 79 Problem 8. (10 points) Find the number of inversions in the following array without applying brute force. You may want to note that the first 10 items are sorted in reverse order and the last 10 items are sorted in order. Show enough work or explanation to see that you aren't using an O(n²) brute force algorithm. 81 77 73 69 66 62 52 41 36 23 12 31 33 57 61 68 75 76 78 79

Answer rating: 100% (QA)

To find the number of inversions in the array efficiently you can use a divideandconquer approach li... View the full answer