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

DOI10.1080/00207160.2012.659246zbMath1371.68122OpenAlexW2092410491MaRDI 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 pointquasi-metricQuicksortcomplexity spacecomplexity classimproverHanoiLargetwoworsener

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Complete metric spaces (54E50) Metric spaces, metrizability (54E35) Fixed-point and coincidence theorems (topological aspects) (54H25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

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

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

This page was built for publication: New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces