New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces

DOI10.1080/00207160.2012.659246zbMath1371.68122MaRDI QIDQ4903466

No author found.

Publication date: 22 January 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10251/46842

zbMATH Keywords

fixed point; quasi-metric; Quicksort; complexity space; complexity class; improver; Hanoi; Largetwo; worsener

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

54E50: Complete metric spaces

54E35: Metric spaces, metrizability

54H25: Fixed-point and coincidence theorems (topological aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, On Fixed Point Theory in Partially Ordered (Quasi-)metric Spaces and an Application to Complexity Analysis of Algorithms, Qualitative versus quantitative fixed point techniques in computer science, A new contribution to the fixed point theory in partial quasi-metric spaces and its applications to asymptotic complexity analysis of algorithms, Complexity analysis via approach spaces, New results on the Baire partial quasi-metric space, fixed point theory and asymptotic complexity analysis for recursive programs, On Matthews' relationship between quasi-metrics and partial metrics: an aggregation perspective, Fixed point theorems in generalized metric spaces with applications to computer science, Metric aggregation functions revisited, On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms, On quasi-metric aggregation functions and fixed point theorems

Cites Work

• Unnamed Item
• The Baire partial quasi-metric space: a mathematical tool for asymptotic complexity analysis in computer science
• Applications of the complexity space to the general probabilistic divide and conquer algorithms
• An extension of the dual complexity space and an application to computer science
• Sequence spaces and asymmetric norms in the theory of computational complexity.
• Quasi-metric properties of complexity spaces
• The complexity space of partial functions: a connection between complexity analysis and denotational semantics
• Difference Equations
• Towers of Hanoi and Analysis of Algorithms
• The Smyth Completion
• Denotational semantics for programming languages, balanced quasi-metrics and fixed points
• On the structure of the space of complexity partial functions