Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Unless this was postively known to be a performance bottleneck, I would just throw the default library quicksort implementation at it and not worry further. –  Henning Makholm Sep 30 '11 at 18:23
    
@Henning: In other words, you're ignoring the question. –  TonyK Sep 30 '11 at 20:24
    
@Tony, he asked me how I would sort the various lists, and I answered truthfully to the best of my ability. –  Henning Makholm Sep 30 '11 at 21:05
    
@Henning: Well duh. In other other words, you're disparaging the question. So I just voted it up. –  TonyK Sep 30 '11 at 21:07

2 Answers 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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.