Scott’s Qualitative Fixed Point Technique in Complexity Analysis of Algorithms

In 1972, D.S. Scott developed a qualitative mathematical technique for modeling the meaning of recursive specifications in Deno-tational Semantics. In this paper we show that the same original Scott's technique remains helpful for Asymptotic Complexity Analy-sis of algorithms requiring really a reduced number of hypotheses and elementary arguments. Thus, we will disclose that such a qualitative approach presents a uni ed mathematical method that is useful for Asymptotic Complexity Analysis and Denotational Semantics. More-over, we will emphasize the introduced technique applying the results to provide the asymptotic complexity (upper and lower bounds) of the running time of computing of a celebrated algorithm. 2010 AMS Classification: 47H10, 54F05, 68N30, 68Q55, 68Q25, 68W40