{"id":2642,"date":"2009-07-01T15:00:00","date_gmt":"2009-07-01T13:00:00","guid":{"rendered":"https:\/\/forschungsnetzwerk-chim.de\/?post_type=publikationen&#038;p=2642"},"modified":"2024-01-26T12:01:50","modified_gmt":"2024-01-26T11:01:50","slug":"an-%cf%89n-log-n-lower-bound-for-computing-the-sum-of-even-ranked-elements","status":"publish","type":"publikationen","link":"https:\/\/forschungsnetzwerk-chim.de\/en\/publications\/an-%cf%89n-log-n-lower-bound-for-computing-the-sum-of-even-ranked-elements\/","title":{"rendered":"An \u03a9(n log n) lower bound for computing the sum of even-ranked elements"},"content":{"rendered":"\n<p>Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove that, in the algebraic computation-tree model, this problem has time complexity \\Theta(n log n). This solves an open problem posed by Michael Shamos at the Canadian Conference on Computational Geometry in 2008.<\/p>\n","protected":false},"excerpt":{"rendered":"<p><b>Publication:<\/b> 2009<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"_acf_changed":false},"beteiligte":[],"class_list":["post-2642","publikationen","type-publikationen","status-publish","hentry","publikationen_category-chemistry"],"acf":[],"_links":{"self":[{"href":"https:\/\/forschungsnetzwerk-chim.de\/en\/wp-json\/wp\/v2\/publikationen\/2642","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forschungsnetzwerk-chim.de\/en\/wp-json\/wp\/v2\/publikationen"}],"about":[{"href":"https:\/\/forschungsnetzwerk-chim.de\/en\/wp-json\/wp\/v2\/types\/publikationen"}],"wp:attachment":[{"href":"https:\/\/forschungsnetzwerk-chim.de\/en\/wp-json\/wp\/v2\/media?parent=2642"}],"wp:term":[{"taxonomy":"beteiligte","embeddable":true,"href":"https:\/\/forschungsnetzwerk-chim.de\/en\/wp-json\/wp\/v2\/beteiligte?post=2642"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}