911 views
7 votes
7 votes
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.

1 Answer

Related questions

32 votes
32 votes
5 answers
1
go_editor asked May 23, 2016
6,640 views
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:$O(nm \log m)$$O(mn \log n)$...