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:
b) $f(n)=O(\log n)$
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.