Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements
| dc.creator | Thite, Shripad | |
| dc.date | 2006-06-08 | |
| dc.date.accessioned | 2026-07-07T07:13:02Z | |
| dc.date.available | 2026-07-07T07:13:02Z | |
| dc.description | 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. | |
| dc.description | 3 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0606038 | |
| dc.identifier | http://arxiv.org/abs/cs/0606038 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112294 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements | |
| dc.type | text |