3
$\begingroup$

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order.

How would you sort the whole list given the following:

a) $f(n)=O(1)$

b) $f(n)=O(\log n)$

c) $f(n)=O(n^{1/2})$

d) How big can $f(n)$ be for the list to remain sortable in $O(n)$ time?

I hope somebody can help, thanks in advance.

  • 0
    @Henning: Well duh. In *other* other words, you're disparaging the question. So I just voted it up.2011-09-30

2 Answers 2

2

You can sort the unordered elements in time $O(f(n) \log f(n))$, and then merge the two lists in time $O(\max (n, f(n)))$. So this gives you $O(n)$ as long as $f(n) \log f(n) = O(n)$, which I think answers d).

The trouble with a) is this: With a binary search, you can find the positions to insert the unordered elements in $O(\log n)$ time; but physically inserting them in the list takes $O(n)$ time, because you have to shift all those elements up by one. The same applies, mutatis mutandis, to b) and c).

0

I am assuming f(n) is the number of unordered elements in the list. I don't understand the significance of O of f(n), so maybe I don't understand the problem.

You can sort the unordered elements separately using a sort O(f(n) log f(n)) and then merge them with the ordered elements in an O(n) operation. In order to sort the entire list in O(n) time, I believe the unordered list would have to be already sorted, so f(n) would have to be 0 or 1.