{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:13Z","timestamp":1750306873917,"version":"3.41.0"},"reference-count":6,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Inroads"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>The most common measure for an algorithm's efficiency is its running time, described as a function of the input length. Traditionally, however, several inconsistencies have found their way even to the analysis of the most classical algorithms. In some cases these are 'slight' inconsistencies, in the sense that their effect may change the result by a factor of lgn. Some others have a polynomial effect, and on the extreme---an exponential one. We discuss this matter, bringing pairs of examples for each of the categories of effect. In the first member of the pair, the algorithm's running time is calculated accurately, whereas in the other member, it is analyzed incorrectly, demonstrating that the computing community is being inconsistent when it comes to algorithm analysis. The article's intention is not to ask authors of textbooks on algorithms to produce modified editions of their books. Rather, it wishes to raise the question of inconsistency in our treatment of algorithm analysis among various algorithms.<\/jats:p>","DOI":"10.1145\/2432596.2432615","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"52-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On consistent inconsistencies"],"prefix":"10.1145","volume":"4","author":[{"given":"Amir","family":"Sapir","sequence":"first","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Brassard G. and Bratley P. Fundamentals of Algorithmics. (New Jersey: Prentice Hall 1996): chapter 7.7.  Brassard G. and Bratley P. Fundamentals of Algorithmics . (New Jersey: Prentice Hall 1996): chapter 7.7."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_3_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. Stein C. Algorithms. (Cambridge Massachusetts: MIT 2009).  Cormen T. H. Leiserson C. E. Rivest R. L. Stein C. Algorithms . (Cambridge Massachusetts: MIT 2009)."},{"key":"e_1_2_1_4_1","first-page":"293","article-title":"Multiplication of multidigit numbers on automata","volume":"145","author":"Karatsuba A. A.","year":"1962","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_5_1","unstructured":"Papadimitriou C. Vazirani U. Dasgupta A. Algorithms. (New York: McGraw-Hill 2008).  Papadimitriou C. Vazirani U. Dasgupta A. Algorithms . (New York: McGraw-Hill 2008)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"}],"container-title":["ACM Inroads"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432596.2432615","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432596.2432615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:20Z","timestamp":1750234700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432596.2432615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":6,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2432596.2432615"],"URL":"https:\/\/doi.org\/10.1145\/2432596.2432615","relation":{},"ISSN":["2153-2184","2153-2192"],"issn-type":[{"type":"print","value":"2153-2184"},{"type":"electronic","value":"2153-2192"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2013-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}