It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list of $n$ sorted elements. How much time does it take to find the median of $2n$ elements which are given as two lists of $n$ sorted elements each?
- $O (1)$
- $O \left(\log n\right)$ but not $O (1)$
- $O (\sqrt{n})$ but not $O \left(\log n\right)$
- $O (n)$ but not $O (\sqrt{n})$
- $O \left(n \log n\right)$ but not $O (n)$