2,409 views

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?

1. $O (1)$
2. $O \left(\log n\right)$ but not $O (1)$
3. $O (\sqrt{n})$ but not $O \left(\log n\right)$
4. $O (n)$ but not $O (\sqrt{n})$
5. $O \left(n \log n\right)$ but not $O (n)$

finding median of n elements (unsorted) takes O(n) time so for 2n elements also it will be O(n)
CORMEN Exercise problem

chapter-9 medians and order statistics page no-223  9.3-8

1. Calculate the medians $m1$ and $m2$ of the input arrays $ar1[\ ]$ and $ar2[ \ ]$ respectively.
2. If $m1$ and $m2$ both are equal,
return $m1$ (or $m2$)
3. If $m1$ is greater than $m2$, then median is present in one of the below two subarrays.
(a)  From first element of $ar1$ to $m1$ $(ar1[0$ to $n/2])$
(b)  From $m2$ to last element of $ar2$  $(ar2[n/2$ to $n-1])$
4. If $m2$ is greater than $m1$, then median is present in one of the below two subarrays.
(a)  From $m1$ to last element of $ar1$  $(ar1[n/2$ to $n-1])$
(b)  From first element of $ar2$ to $m2$ $(ar2[0$ to $n/2])$
5. Repeat the above process until size of both the subarrays becomes $2$.
6. If size of the two arrays is $2$ then,
Median $= (\max(ar1[0], ar2[0]) + \min(ar1[1], ar2[1]))/2$
Time complexity $O(\log n)$

http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

Correct Answer: $B$

1. Merge sort is having O(nlogn), simply merging two sorted arrays take only O(n)
2. When we can achieve TC as logn, why will we go for nlogn?
@vaibhavkedia968 2 sorted arrays after merging doesn’t guarantees that they are by default getting sorted. For eg. {11,18,22,31,40}  and {23,45,57,67,82}.
I am not getting it how it is O(logn) from this algo I am getting  O(n) time ??
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://gateoverflow.in/25774/tifr-cse-2013-part-b-question-12", "fetch_time": 1675042141000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-06/segments/1674764499790.41/warc/CC-MAIN-20230130003215-20230130033215-00435.warc.gz", "warc_record_offset": 292414051, "warc_record_length": 23568, "token_count": 686, "char_count": 1940, "score": 4.125, "int_score": 4, "crawl": "CC-MAIN-2023-06", "snapshot_type": "latest", "language": "en", "language_score": 0.7848412394523621, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00009-of-00064.parquet"}