Question

You are given two sorted lists of size mandn. Give an $\mathit{O}\mathbf{(}\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{m}\mathbf{+}\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{n}\mathbf{)}$time algorithm for computing the $\mathbf{k}$ th smallest element in the union of the two lists.

Short answer

The algorithm of computing kth smallest element is explained in time bound $O(\log m+\log n)$.

Step-by-step solution

Answer by Method-I

Here, there will be two sorted listsdescribed size m and n logarithm base computing to display the smallest element union. Here we can see two different types of the answer given below.

1^st type answer is:

Algorithm:

function $smallelement(x[1,\dots ,m],y[1,\dots ,n],k)$

if$m=0$: return $y\left[k\right]$

if$n=0$: return

if$x[m/2]>y[n/2]$:

if$k<(m+n)/2$:

return$smallelement(x[\mathrm{1..}m/2],y[1\dots n],k)$

else:

return ..

else:

if$k<(m+n)/2$:

return $smallelement(x[\mathrm{1..}m/2],y[1\dots n],k)$

else:

return $smallelement(x[(m/2)+\mathrm{1..}m],y[1\dots n],k–m/2)$

This same top half of array$x$ is greater than the bottom halves of both x and yarrays if $x[m/2]$is greater than$y[n/2]$. As a result, the top half of array x must be higher than the median of all aggregated arrays. The complete bottom half of arrayy must be under the merged arrays' median. We can delete one of these two half arrays by evaluating kto$(m+n)/2$.

Running time:$O(\log m+\log n)$, a constant amount of time istaken either mor nsmall halved values. It will happen at most$\log m+\log n$time before one of them reaches zero.