Lower bounds for finding the maximum and minimum elements with k lies

Details Lower bounds for finding the maximum and minimum elements with k lies Lower bounds for finding the maximum and minimum elements with k lies

2011-11-14

arxiv.org/abs/1111.3288v1

Acta Univ. Sapirntiae, Inform. 3, 2 (2011) 224--229

Computer Science

Discrete Mathematics

Scientific paper

In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size $n$ using pairwise comparisons if $k$ of the comparisons might be erroneous where $k$ is a fixed constant. We prove that at least $(k+1.5)n+\Theta(k)$ comparisons are needed in the worst case thus disproving the conjecture that $(k+1+\epsilon)n$ comparisons are enough.

Affiliated with

Also associated with

No associations

Rating

Lower bounds for finding the maximum and minimum elements with k lies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower bounds for finding the maximum and minimum elements with k lies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds for finding the maximum and minimum elements with k lies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218921