Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Encountered this question but I couldn't solve with the complexity they solved it:
Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ inverted pairs, and the middle $n - 2\sqrt[\leftroot{-2}\uproot{2}]{n}$ elemnts are sorted. What is the complexity of sorting the unsorted array?
They claim in the answer that sorting array with $I$ inversions is $O(n\log{\frac{n}{I}})$.Why?
If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log n).
In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n).
And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.
>line prefix or "the"button" in the post editor tool-bar.) Please check the problem statement: there are just so many values of $n$ where $\frac n 5$ does not exceed $1\ldots2 \times \sqrt n$. $\endgroup$