A note on counting independent terms in asymptotic expressions of computational complexity
From MaRDI portal
Publication:1686563
DOI10.1007/S11590-016-1092-7zbMATH Open1385.90034arXiv1512.09363OpenAlexW3099497372MaRDI QIDQ1686563FDOQ1686563
Fabiano de S. Oliveira, Valmir C. Barbosa
Publication date: 15 December 2017
Published in: Optimization Letters (Search for Journal in Brave)
Abstract: The field of computational complexity is concerned both with the intrinsic hardness of computational problems and with the efficiency of algorithms to solve them. Given such a problem, normally one designs an algorithm to solve it and sets about establishing bounds on its performance as functions of the algorithm's variables, particularly upper bounds expressed via the big-oh notation. But if we were given some inscrutable code and were asked to figure out its big-oh profile from performance data on a given set of inputs, how hard would we have to grapple with the various possibilities before zooming in on a reasonably small set of candidates? Here we show that, even if we restricted our search to upper bounds given by polynomials, the number of possibilities could be arbitrarily large for two or more variables. This is unexpected, given the available body of examples on algorithmic efficiency, and serves to illustrate the many facets of the big-oh notation, as well as its counter-intuitive twists.
Full work available at URL: https://arxiv.org/abs/1512.09363
asymptoticscomputational complexityanalysis of algorithmsbig-oh notationexperimental algorithmics and optimization
Cites Work
This page was built for publication: A note on counting independent terms in asymptotic expressions of computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686563)
