Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements

Details Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements

2006-06-08

arxiv.org/abs/cs/0606038v1

Computer Science

Computational Complexity

3 pages

Scientific paper

Let S = be a given vector of n real numbers. The rank of a real z with respect to S is defined as the number of elements s_i in S such that s_i is less than or equal to z. We consider the following decision problem: determine whether the odd-numbered elements s_1, s_3, s_5, ... are precisely the elements of S whose rank with respect to S is odd. We prove a bound of Theta(n log n) on the number of operations required to solve this problem in the algebraic computation tree model.

Affiliated with

Also associated with

No associations

Rating

Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements 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 Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409683