A tight lower bound for selection in sorted X+Y

1. M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest and R.E. Tarjan, "Time bounds for selection", JCSS, 7 (1973), pp 448–461

   Google Scholar 

2. M. Cosnard, J. Duprat and A.G. Ferreira, "The complexity of searching in X + Y and other multisets", Information Processing Letters, 34 (1990) 103–109

   Article  Google Scholar 

3. M.L.Fredman, "Two applications of a probabilistic search technique: sorting X + Y and building balanced search trees", in Proc. 7-th Annual ACM Symp. on Theory of Computing, (May 1975), ACM, 1975, pp 240–244

   Google Scholar 

4. G.N. Frederickson and D.B. Johnson, "The complexity of selection and ranking in X + Y and matrices with sorted columns", JCSS 24 (1982), pp 197–208

   Google Scholar 

5. G.N. Frederickson and D.B. Johnson, "Generalized selection and ranking: sorted matrices", SIAM J. Comput. 13 (1), Feb 1984, pp 197–208

   Article  Google Scholar 

6. L.H. Harper, T.H. Payne, J.E. Savage and E. Straus, "Sorting X + Y", Comm. ACM 18 (6) (1975), pp 347–349

   Article  Google Scholar 

7. J.L.Lambert, Sorting the elements of X+Y with O(n²) comparisons, in Proceedings of STACS 90, Feb. 1990, Rouens, France

   Google Scholar 

8. N. Linial and M. Saks, "Searching ordered structures", Journal of Algorithms 6 (1985), pp 86–103

   Article  Google Scholar 

9. A. Mirzaian and E. Arjomandi, "Selection in X + Y and matrices with sorted rows and columns", Inf. Proc. Letters 20 (1985), pp 13–17

   Article  Google Scholar 

Download references