Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements
<|reference_start|>Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements: Let S = <s_1, s_2, s_3, ..., s_n> 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.<|reference_end|>
@article{thite2006tight,
    title={Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements},
    author={Shripad Thite},
    journal={arXiv preprint arXiv:cs/0606038},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606038},
    primaryClass={cs.CC cs.DS}
}