0
$\begingroup$

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?

$\endgroup$
12
  • $\begingroup$ Welcome to ComputerScience@SE. Please attribute quoted contents properly. (There is Markdown for block quotes: use > 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$
    – greybeard
    Feb 10 '20 at 8:00
  • $\begingroup$ I think $I$ refers to the inversion count not to the number of swaps actually necessary to sort the array. $\endgroup$
    – Albjenow
    Feb 10 '20 at 8:04
  • $\begingroup$ Yes, this is what I meant. $\endgroup$ Feb 10 '20 at 8:13
  • $\begingroup$ Is the problem statement correct? As is you could just sort the $\sqrt{n}$ long prefixes and suffices in $\mathcal{O}(\sqrt{n} \log n)$ time leading to a linear algorithm. $\endgroup$ Feb 10 '20 at 9:10
  • $\begingroup$ That was my answer as well, this is why I'm so confused. $\endgroup$ Feb 10 '20 at 9:14
3
$\begingroup$

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.

$\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.