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 the algorithm’s performance as functions of the relevant input-size descriptors, particularly upper bounds expressed via the big-oh notation. In some cases, however, especially those arising in the fields of experimental algorithmics and optimization, one may have to resort to performance data on a given set of inputs in order to figure out the algorithm’s big-oh profile. In this note, we are concerned with the question of how many candidate expressions may have to be taken into account in such cases. We show that, even if we only considered upper bounds given by polynomials, the number of possibilities could be arbitrarily large for two or more descriptors. This is unexpected, given the available body of examples on algorithmic efficiency, and underlines the importance of careful and meticulous criteria. It also serves to illustrate the many facets of the big-oh notation, as well as its counter-intuitive twists.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
One of the well-known examples of this in the single-variable case is Strassen’s algorithm for multiplying two \(n\times n\) matrices, whose running time is \(O(n^{\log _2 7})\) [8].
References
Goldsmith, S.F., Aiken, A.S., Wilkerson, D.S.: In Proc. ESEC-FSE 2007, pp. 395–404 (2007)
Burnim, J., Juvekar, S., Sen, K.: In Proc. ICSE 2009, pp. 463–473 (2009)
Zaparanuks, D., Hauswirth, M.: In Proc. PLDI 2012, pp. 67–76 (2012)
Coppa, E., Demetrescu, C., Finocchi, I.: IEEE T. Software Eng. 40:1185 (2014)
Hardy, G.H.: Orders of infinity: The ‘infinitärcalcül’ of Paul du Bois-Reymond, 2nd edn. Cambridge University Press, Cambridge (1924)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete mathematics: a foundation for computer science, 2nd edn. Addison-Wesley, Reading (1989)
Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol A–C. Springer, Berlin (2003)
Strassen, V.: Numer. Math. 13:354 (1969)
Regan, K.W.: A polynomial growth puzzle (2015). Gödel’s Lost Letter and P = NP. https://rjlipton.wordpress.com/2015/09/12/a-polynomial-growth-puzzle/
Acknowledgements
The authors acknowledge partial support from Conselho Nacional de Desenvolvimento Científico e Tecnológico, Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ), and a FAPERJ BBP grant.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Oliveira, F.d.S., Barbosa, V.C. A note on counting independent terms in asymptotic expressions of computational complexity. Optim Lett 11, 1757–1765 (2017). https://doi.org/10.1007/s11590-016-1092-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-016-1092-7