GENERALIZED ASYMPTOTIC NOTATIONS VIA FILTERS: A NEW FRAMEWORK FOR ALGORITHM ANALYSIS

Alexander Caicedo     (Pontificia Universidad Javeriana, Departamento de Ingeniería Electrónica, Carrera 7, No. 40–62, Bogotá, 11023, Colombia)
Valentina López-Chacón     (Universidad Politécnica de Valencia, Máster Universitario de Inteligencia Artificial, Reconocimiento de Formas e Imagen Digital, Valencia, 46022, Spain)
Margot Salas-Brown     (Universidad de Los Andes, Departamento de Matemáticas, Carrera 1, No. 18A–12, Bogotá, 111711, Colombia)

Abstract


This paper introduces a  generalization of asymptotic notation using filters, a topological structure. We present key properties of this generalization, including reflexivity, symmetry, and transitivity, supported by illustrative examples. Our research demonstrates that classical asymptotic notations imply their filter-generalized counterparts, but we provide examples showing the converse is not universally true. We also propose a characterization of traditional asymptotic notations using filters, offering a new perspective on these fundamental concepts. Furthermore, we establish relationships between bounded or vanishing sequences and filter-based asymptotic notations, enabling the determination of properties central to this study. This generalization provides a more nuanced framework for analyzing algorithmic complexity, potentially capturing behaviors overlooked by classical notations and opening new avenues for theoretical computer science research.

Keywords


Asymptotic notation, Filters, Sequences

Full Text:

PDF

References


  1. Akin E. Recurrence in Topological Dynamics. Furstenberg Families and Ellis actions. Univ. Ser. Math. New York: Plenum Press, 1997. 266 p. DOI: 10.1007/978-1-4757-2668-8
  2. Akomolafe D.T., Nwanz N.M. Deployment of an efficient algorithm for searching motor vehicle database. Asian J. Adv. Res., 2021. Vol. 10, No. 4. P. 18–26.
  3. Bernstein A.R. A new kind of compactness for topological spaces. Fund. Math., 1970. Vol. 66, No. 2. P. 185–193. DOI: 10.4064/fm-66-2-185-193
  4. Folea R., Slusanschi E. A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times. In: 23rd Int. Conf. Control Systems and Computer Science (CSCS), 26–28 May 2021, Bucharest, Romania. IEEE Xplore, 2021. P. 157–164. DOI: 10.1109/CSCS52396.2021.00033
  5. Frolík Z. Sums of ultrafilters. Bull. Amer. Math. Soc., 1967. Vol. 73. P. 87–91.
  6. Furstenberg H. Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton: Princeton Univ. Press, 1981. 202 p.
  7. Goldreich O. Computational complexity: a conceptual perspective. ACM Sigact News, 2008. Vol. 39, No. 3. P. 35–39. DOI: 10.1145/1412700.1412710
  8. Lim T.S., Loh W.Y., Shih Y.S. A comparison of prediction accuracy, complexity, and training time of thirty-three old and new classification algorithms. Mach. Learn., 2000. Vol. 40, No. 3. P. 203–228. DOI: 10.1023/A:1007608224229
  9. Mogoş A., Mogoş B., Florea A. A method to compare two complexity functions using complexity classes. U.P.B. Sci. Bull., Series A, 2010. Vol. 72, No. 2. P. 69–84.
  10. Mogoş A., Mogoş B., Florea A. A new asymptotic notation: weak theta. Math. Probl. Eng., 2015. Vol. 2015. Art. no. 912962. 15 p. DOI: 10.1155/2015/912962
  11. Ramesh V.P., Gowtham R. Asymptotic notations and its applications. Math. Newsl., 2017. Vol. 28, No. 4. P. 10–16.
  12. Russell S., Norvig P. Artificial Intelligence: a Modern Approach. 3rd ed. Upper Saddle River: Prentice–Hall, 2010. 1152 p.
  13. Thomas C., Leiserson C.E., Stein C. Introduction to Algorithms, 3rd. 2009. 1312 p.
  14. van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity. Cambridge: MIT Press, 1990. 1016 p.




DOI: http://dx.doi.org/10.15826/umj.2025.2.005

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.