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.
On
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).
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.