Abstract
In Cerdà-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012), a newmathematical fixed point technique, that uses the so-called Baire partial quasi-metricspace, was introduced with the aim of providing the asymptotic complexity of a class ofrecursive algorithms. The aforementioned technique presents the advantage that requiresless calculations than the quasi-metric original one given by Schellekens (Electron. NotesTheor. Comput. Sci. 1:211-232, 1995). In this paper we continue the study, started inCerdà-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012), on the use ofpartial quasi-metric spaces for asymptotic complexity analysis of algorithms. Concretely,our main purpose is to prove that the Baire partial quasi-metric space is an appropriatemathematical framework for discussing via fixed point arguments the asymptotic complexityof a general class of recursive algorithms to which all the algorithms analyzed inCerdà-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012) belong. Theobtained results are illustrated by means of applying them to yield the complexity of twocelebrated recursive algorithms which don not belong to the class discussed inCerdà-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012).
MSC: 47H10, 54E50, 68Q15, 68Q25, 68W40.
Similar content being viewed by others
1 Introduction
In 1994, Matthews introduced the notion of partial metric space in order to obtain a newmathematical framework to model computational recursion processes in program verification bymeans of ‘metric’ fixed-point techniques [1]. Moreover, he gave an application of this new metric structure to parallelcomputing by means of a partial metric version of the celebrated Banach fixed-point theoremin [2]. Later on, in 1995, Schellekens introduced the (quasi-metric) complexity space asa new mathematical approach of the foundation for the asymptotic complexity analysis ofalgorithms [3]. The applicability of this theory to the asymptotic complexity analysis of Divideand Conquer algorithms was also illustrated by Schellekens, in the same reference, usingfixed-point arguments based on the use of a quasi-metric version of the aforementionedBanach fixed-point theorem.
Motivated by the utility of quasi-metric spaces for the asymptotic complexity analysis ofalgorithms via fixed-point techniques and the usefulness of partial metric spaces to analyzeprogram correctness, the possibility of analyzing the asymptotic complexity of algorithmsvia Matthews’ fixed-point theorem was discussed recently in [4]. However, in the aforesaid reference it was shown that, at first, such ananalysis cannot be carried out through the aforementioned result. In consequence, in thepreceding reference a new mathematical tool, which was called the Baire partial quasi-metricspace, was introduced in order to provide a novel mathematical framework for the asymptoticcomplexity analysis of algorithms which unify, under the same framework, the quasi-metricfixed-point arguments originating with the Schellekens approach and the seminal ideas ofMatthews on partial metric spaces. The mathematical framework based on the Baire partialquasi-metric space presents the advantage of providing the complexity of the algorithmsunder consideration through easier and fewer calculations than those given in theSchellekens methods. In [4], the applicability of the Baire partial-quasi-metric fixed-point techniques wereillustrated discussing the complexity of a few particular and celebrated recursivealgorithms. Nevertheless, in the class of recursive algorithms there are some whosecomplexity cannot be analyzed be means of the fixed-point techniques developed in [4]. Examples of this kind of algorithms are the well-know algorithms that solves theTowers of Hanoi puzzle and the algorithm that computes the value of the Fibonacci sequence,which we will call Hanoi and Fibonacci, respectively, in the following.
In this paper we continue and improve the study started in [4] of the use of partial quasi-metrics for asymptotic complexity analysis ofalgorithms. Concretely, our main purpose is to prove that the Baire partial quasi-metricspace is a suitable mathematical framework for discussing by means of fixed-point argumentsthe asymptotic complexity of a general class of recursive algorithms to which the Hanoi,Fibonacci and all the algorithms analyzed in [4] belong.
The remainder of the paper is organized as follows: Section 2 is devoted, on the onehand, to recall the basics on asymptotic complexity analysis of algorithms and, on the otherhand, to introduce the reader to the associated current metric fixed-point tools.Concretely, we recall briefly, with the aim of motivating our subsequent work, theSchellekens fixed-point method and how it can be applied to the complexity analysis of someDivide and Conquer algorithms. Moreover, the fundamentals on partial metric spaces and theirutility in complexity analysis of algorithms are also discussed. Furthermore, in the samesection, we recall, according to [4], how both frameworks, the quasi-metric and the partial metric one, are unified inorder to construct a new mathematical approach, the so-called Baire partial quasi-metricspace, which preserves the original Schellekens ideas and allows to apply the Matthewsseminal ones to complexity analysis. In Section 3, our new results are presented. Inparticular, we introduce a new fixed-point technique based on the Baire partial quasi-metricspace that extends the provided one in [4] and, in addition, allows to provide easily the complexity of some algorithmswhich cannot be analyzed by means of the aforementioned technique given in [4]. Finally, we validate the developed theory applying it to an analysis andretrieving the asymptotic complexity of the celebrated Hanoi and Fibonacci.
2 The asymptotic complexity analysis of algorithms and metric fixed-point tools
2.1 The fundamentals
From now on, and ℕ will denote the set of nonnegative real numbersand the set of positive integer numbers, respectively.
In complexity analysis of algorithms, the running time of computing, that is the timetaking by an algorithm in order to solve the problem for which it has been designed, playsa crucial role (see, for instance, [5]). Usually there are several algorithms that are able to solve a fixed problem.Thus, in a natural way, the complexity analysis focus its interest on determining which ofthem has less complexity, that is which takes less running time of computing. In order tocompare the complexity of all algorithms solving the same problem, the running time ofcomputing of each algorithm is denoted by a function in such a way that represents the time taken by the algorithm to solve theproblem under consideration when the input of the algorithm is of size n. Hence,one can compare the running time of computing all the aforesaid algorithms by means of thecomparison of their associated functions.
Nevertheless, given an algorithm, to asses which is the function that describes itsrunning time of computing for every input size is, in many cases, a hard challenge. Forthis reason, in most situations it is enough to work, in order to compare the algorithmcomplexity, with an approximate running time of computing of each algorithm to becompared. To provide the running time of computing of algorithms in an approximate way isthe main objective of the so-called asymptotic complexity analysis of algorithms.
In what follows we recall a few pertinent notions from asymptotic complexity analysiswhich will be a crucial role in our subsequent work. To this end, we will denote by the set of all functions from ℕ into.
Let denote the running time of computing of a concrete algorithm.Moreover, given a certain function , consider that there exist and satisfying for all with (of course ≤ stands for the usual order on). Hence, it is clear that the function g provides anasymptotic upper bound of the running time f of the algorithm underconsideration. Therefore, if we do not have exact information as regards the expression ofthe function f, then the function g yields us an‘approximate’ information of the running time of computing f in sucha way that the considered algorithm takes a time to solve the problem boundedasymptotically above by g. Following the standard notation, we will write provided that and g is an asymptotic upper bound off.
Of course, an asymptotic upper bound itself does not provide much information on thecomplexity f of the algorithm under study. In order to give a tighter bound onthe complexity f, in asymptotic complexity analysis of algorithms are used inaddition asymptotic lower bounds of the running time of computing. Concretely, a function provides an asymptotic lower bound of the unknown runningtime of computing f under consideration provided that there exist and such that for all with . When h is an asymptotic lower bound of fwe will denote it, as usual, by .
Therefore when we have found two functions such that , we obtain, through h and g, a completeasymptotic information about the time f taken by the algorithm under discussion.Moreover, in case of f obeying the condition , for any , we will say that is the complexity class of f. Furthermore, we willdenoted the complexity class of f by provided the existence of a function such that .
Accordingly, the main aim of the asymptotic complexity analysis is to describe therunning time of algorithms by means of determining its asymptotic complexity class.
2.2 The Schellekens approach and the quasi-metric complexity space
According to [6], and following modern terminology, a quasi-metric space is a pair such that X is a non-empty set and d is aquasi-metric on X, where by a quasi-metric we mean a function such that for all :
-
(i)
;
-
(ii)
.
Clearly, a metric space is a quasi-metric space in such a way that d satisfies the next additionalcondition for all :
-
(iii)
.
It is well known that each quasi-metric d on X generates a-topology on X which has as a base the family of opend-balls , where for all and . Moreover, a quasi-metric space is called bicomplete if the metric space is complete, where the metric is defined for all by .
In 1995, as we have mentioned in Section 1, Schellekens introduced the so-calledcomplexity space with the aim of developing a mathematical foundation for the asymptoticcomplexity analysis of algorithms [3]. Let us recall that the complexity space consists of the pair, where
and is the bicomplete quasi-metric on defined by
Of course in equation (1) the convention that is adopted.
Although in asymptotic complexity analysis of algorithms the running time of computing isrepresented by means of functions in and, thus, the condition ‘’ in not required, according to [3], every reasonable algorithm, from a computability point of view, must obey theaforementioned condition. Hence each algorithm can be associated with a function belongingto whichrepresents, as a function of the input size, its running time of computing.
The utility of the complexity space in algorithm complexity is given, in part, by thecomputational interpretation of the numerical value . Concretely, given two functions , the complexity distance from f to g, thatis , provides information about the relative progress made inlowering the complexity by replacing any program A with complexity functionf by any program B with complexity function g in such a waythat if , the fact that can be interpreted as the program A is at least asefficient as the program B. In fact, the condition implies that .
It must be stressed that the asymmetry of is key in order to provide information about the increase ofcomplexity whenever an algorithm is replaced by another one. Of course, a metric wouldgive at most information on the increase but it would not be able to provide whichalgorithm of both, A or B, is more efficient.
In [3], Schellekens gave an application of the complexity space to asymptoticcomplexity analysis. In particular, he gave a new method, based on the use of thecelebrated Banach fixed-point theorem, to analyze the running time of computing of Divideand Conquer algorithms.
In what follows we recall briefly the aforesaid method, since this will allow the readerto gain a better understanding of the motivation for our subsequent work (exposed inSection 3). To this end, let us recall that the Banach fixed-point theorem can bestated in the quasi-metric framework as follows.
Theorem 1 Let f be a mapping from a bicomplete quasi-metric space into itself such that there exists satisfying
for all . Then f has a unique fixed point.
In many cases, the recursive structure of a Divide and Conquer algorithm yields theresult that its running time of computing satisfies the recurrence equation
where with , , and with for all .
Observe that for Divide and Conquer algorithms, it is sufficient to obtain the complexityon inputs of size n with n ranges over the set (for a fuller treatment we refer the reader to [5]).
In order to provide the running time of computing of a Divide and Conquer algorithmsatisfying the recurrence equation (2), we have to prove that the recurrence equation hasa unique solution, which represents the running time, and, in addition, we have to computethe asymptotic complexity class of such a solution. As we show in the following, theannounced Schellekens method is able to prove that equation (2) has a unique solution andto yield an asymptotic upper bound (asymptotic lower bounds of the running time of Divideand Conquer algorithms were obtained by Schellekens following standard arguments which arenot based on the use of fixed-point techniques):
Denote by the subset of given by
Then the quasi-metric space is bicomplete, since the quasi-metric space is bicomplete (see [7] for the bicompleteness of ) and the set is closed in .
Next, given the recurrence equation (2), we introduce the functional as follows:
It is clear that a function in is a solution to the recurrence equation (2) if and only ifit is a fixed point of the functional . Then, it is not hard to check that
for all . Consequently, Theorem 1 guarantees the existence of aunique fixed point of and, thus, the existence and uniqueness of the solution tothe recurrence equation (2). Of course such a solution provides a unique possiblerepresentative of the running time.
In order to approximate, according to the Schellekens approach, the running time ofcomputing of the algorithms under consideration it remains to give an asymptotic upperbound of . But Schellekens proved that provided that and that .
The preceding facts mentioned allow us to state the next useful result [3].
Theorem 2 A Divide and Conquer recurrence equation of the form (2) has a uniquesolution in . Moreover if there exists such that the functional associated with equation (2) obeys , then .
With the aim of illustrating the real utility of Theorem 2, Schellekens applied itto provide a description of an asymptotic upper bound of the running time of computing ofMergesort (for a detailed discussion of Mergesort see, for instance, [5]). Specifically, he gave a new proof of the well-known fact that the (average)running time of computing of Mergesort is in .
2.3 The partial metric space approach
In 1994, as we have announced in Section 1, Matthews introduced partial metricspaces with a twofold objective [1]. On the one hand, he claimed to present a new mathematical framework to modelcomputational recursion processes, in the spirit of Scott (see [8] for details of Scott theory), in program verification by means of‘metric’ fixed-point techniques. On the other hand, in order to achieve thelater purpose, he wanted to obtain an extension of Banach’s fixed-point theorem tothe partial metric context.
Let us recall a few basic notions about partial metric spaces in order to introduce theMatthews fixed-point theorem.
Following [1], a partial metric space is a pair such that X is a non-empty set X andp is a function satisfying for all :
-
(i)
;
-
(ii)
;
-
(iii)
;
-
(iv)
.
Of course, a metric on a non-empty set X is a partial metric p onX satisfying, in addition, the following condition for all:
-
(v)
.
It is well known that each partial metric p on X generates a topology on X which has as a base the family of openp-balls , where for all and . Moreover, as a consequence, a sequence in a partial metric space converges to a point with respect to .
With the aim of introducing a partial metric version of the Banach fixed-point theorem,Matthews defined the notion of completeness in partial metric spaces. In particular, andaccording to [1], a sequence in a partial metric space is called a Cauchy sequence if exists. A partial metric space is said to be complete if every Cauchy sequence in X converges, with respect to, to a point such that .
The announced new fixed-point theorem can be stated for partial metric spaces asfollows.
Theorem 3 Let f be a mapping from a complete partial metric space into itself such that there is satisfying
for all . Then f has a unique fixed point. Moreover if is the fixed point of f, then .
It is interesting to point out that Matthews used the preceding result to provide asuitable test for lazy data flow deadlock in Kahn’s model of parallel computation(for a fuller treatment of the application we refer the reader to [2]).
In [4], motivated by the usefulness of partial metric spaces in some fields inComputer Science, it was wondered whether partial metric spaces are also useful, likequasi-metric spaces, in asymptotic complexity analysis in the spirit of Schellekens.Hence, in the same reference it was noted that although the set can be endowed with the partialmetric defined in [9] for all by
Matthews fixed-point theorem cannot be directly applied to a discussion of thecomplexity class of the running time of algorithms through . Concretely, in spite of the partial metric space being complete, it was proved that the condition
does not hold for any , where is the functional associated to the recurrence equation (2)and introduced in Section 2.2. Hence, the Matthews fixed-point theorem cannot beapplied to an analysis of the running time of computing of the Divide and Conqueralgorithms whose running time obeys equation (2).
At this point, it seems natural to wonder if another choice of the partial metric couldallow to use Matthews fixed-point theorem for the purpose of discussing running time ofcomputing in asymptotic complexity analysis of algorithms. However, it is interesting tonote that the partial metric , as defined before, is the most natural partial metric thatcan be defined on the set because is induced by in the sense that, for all ,
and, hence, .
Inspired by the fact that Matthews fixed-point theorem does not constitute a suitabletool for the aforementioned purpose, a thorough study of the possibility of applying thepartial metric to asymptotic complexity analysis of algorithms has been donerecently in [10]. In particular, new fixed-point theorems which differ from the Matthews onehave been proved in such a way that they provide a new mathematical basis to carry out anasymptotic complexity analysis of algorithms via partial metrics (concretely via).
2.4 The Baire partial quasi-metric space approach
Since Theorem 3 cannot be used to analyze the complexity of those algorithms whoserunning time of computing is the solution to a recurrence equation (2), the Baire partialquasi-metric space was introduced in [4]. This new mathematical structure allows us to carry out the asymptoticcomplexity analysis of algorithms in the spirit of Schellekens but now involving theoriginal fixed-point arguments of Matthews.
In order to introduce the aforementioned Baire partial quasi-metric space and theassociated fixed-point technique for complexity analysis developed in [4], let us first recall some basics on partial quasi-metrics.
Following [11], a partial quasi-metric space is a pair where X is a non-empty set and q is apartial quasi-metric on X. By a partial quasi-metric we mean a function such that for all :
-
(i)
;
-
(ii)
;
-
(iii)
;
-
(iv)
and .
Of course, a partial metric on a set X is a partial quasi-metric satisfying inaddition the condition:
-
(v)
for all .
Similarly to the case of partial metric spaces a partial quasi-metric qgenerates a -topology on X which has as a base the family of openq-balls , where for all and .
On account of [11], and similarly to the partial metric case, each partial quasi-metric qon X induces a quasi-metric in the following way:
for all . Moreover, a partial quasi-metric space is said to be complete provided that the associatedquasi-metric space is bicomplete.
The Matthews fixed-point theorem, Theorem 3 in Section 2.3, was extended to thecontext of partial quasi-metric spaces as follows [11].
Theorem 4 Let f be a mapping from a complete partial quasi-metric space into itself such that there is , satisfying
for all . Then f has a unique fixed point. Moreover if is the fixed point of f, then .
It is worth to point out that generalizations of the preceding result have been obtainedfor a few type of contractions in partial quasi-metrics spaces in [12] and [13], recently.
In the light of the exposed notions, and according to [4], the Baire partial quasi-metric space can be introduced as follows.
Let Σ be a non-empty alphabet endowed with a partial order ⪯. Denote by the set of all finite and infinite sequences (words) overΣ. Moreover, if denote by the length of x (). Furthermore, given , we will say that x is a subprefix of y,denoted by , provided that and for all .
Set whenever there exists such that , for all , and otherwise. Then the Baire partial quasi-metric space is thecomplete partial quasi-metric space , where is defined by
for all .
As announced before, the Baire partial quasi-metric was introduced in order to apply, insome sense, partial metric fixed-point arguments to asymptotic complexity analysis ofalgorithms. Concretely, the new partial quasi-metric structure was applied successfully todiscussion of the asymptotic complexity of algorithms whose running time of computing istypically given by the recurrence equation
with and such that for all .
More specifically, the utility in asymptotic complexity analysis of the fixed-pointtechnique developed in [4] lies in the following result.
Theorem 5 Let . Fix and with and for all with . Let be the subset of given by and let be the mapping defined by
Then has a unique fixed point . Moreover, . Furthermore, if such that then .
The new mathematical technique that follows from Theorem 5 is provided by the resultbelow.
Corollary 6 Let and let be the functional associated to recurrence equation (6) and given by
for all . Then the following assertions hold:
-
(1)
A recurrence equation of the form (6) has a unique solution .
-
(2)
If there exists such that , then .
In the light of the preceding results, it should be pointed out that they allow one toprovide, via fixed-point techniques, an asymptotic upper bound of the running time ofcomputing of those algorithms under consideration but not its complexity class (accordingto the Schellekens approach exposed in Section 2.2). Moreover, they allow to achievethis without assuming the condition ‘ for all ’, which is an advantage with respect to the Schellekensapproach.
3 The new results
It is clear that the running time of computing of all recursive algorithms does not satisfynecessarily the recurrence equation (6). In fact, there are recursive algorithms whoserunning time of computing obeys the recurrence equation
where such that for all , , , and for all .
Two well-known examples of recursive algorithms whose running time satisfies the precedingrecurrence equation are the algorithm that solves the Towers of Hanoi puzzle, which we willcall Hanoi, and the algorithm that computes the value of the Fibonacci sequence at any givenindex n with , which we will call Fibonacci. Concretely, the running time ofcomputing of Hanoi satisfies the next recurrence equation
where . Moreover, the running time of computing of Fibonacci satisfiesthe recurrence equation
where .
Obviously, the recurrence equations (9) and (10) can be retrieved as a particular case ofthe recurrence equation (8). Observe, also, that the recurrence equation (6) can beretrieved from the recurrence equation (8). For a fuller treatment of Hanoi and Fibonacci werefer the reader to [14].
In [15] and [16], the Schellekens approach, exposed in Section 2.2, was extended and a newfixed-point technique based on the use of the (quasi-metric) complexity space was introducedin order to provide the complexity class of those recursive algorithms with running timesatisfying the recurrence equation (8). The aforesaid technique was applied successfully toyield lower and upper asymptotic complexity bounds of Hanoi and Fibonacci in the samereferences. However, such a quasi-metric fixed-point technique involves arduous computations(see, for instance, Theorem 5 in [15] and Theorem 5 in [16]) when compared with the technique based on the Baire partial quasi-metric andgiven by Theorem 5.
Motivated, on the one hand, by the fact that Theorem 5 is not able to provide thecomplexity class of algorithms like Hanoi and Fibonacci and, on the other hand, by the factthat the Baire partial quasi-metric allows one to develop fixed-point techniques thatrequire fewer and easier calculations than those involved by the Schellekens approach andexposed in [15] and [16], in this section we introduce a new mathematical technique based on the Bairepartial quasi-metric, given by Theorem 9, which extends the technique provided byTheorem 5 and, in addition, allows to provide easily, by means of Theorem 11, theasymptotic class of those recursive algorithms whose running time satisfies the recurrenceequation (8).
3.1 The new fixed-point technique
In order to present the announced technique we need to introduce the followinglemmata.
Lemma 7 Let , and . Let be the subset of given by . Then is closed in .
Proof Suppose that is a sequence in which converges to w in . First of all we prove that . Indeed, assume that . Then taking we find that there exists such that
for all . Since and for all we obtain from inequality (11)
which is a contradiction. So .
Next we show that for all . To this end, assume that there exists with such that for all and . We distinguish two possible cases:
Case 1. . It is clear that for all n. Taking we have guaranteed the existence of such that
for all , since converges to w in . Hence
which is impossible.
Case 2. . Then, given , there exists such that
for all . Whence
for all . Hence
It follows that , which is impossible.
Consequently for all and, thus, . Therefore is closed in . □
Lemma 8 Let f be a mapping from a complete partial quasi-metric space into itself such that there is satisfying
for all . Then f has a unique fixed point x. Moreover, the following assertions hold:
-
(1)
If there exists such that then .
-
(2)
If there exists such that then .
Proof First of all we note that the existence and uniqueness of the fixed pointx of f is guaranteed by Theorem 4.
(1) Assume for the purpose of contradiction that . Then the inequality (14) yields
It follows that , which is a contradiction.
(2) Similar arguments to those given in the proof of (1) apply to the proof of assertion (2). □
The next result provides the mathematical foundations for the fixed-point techniqueuseful for analyzing the complexity class of recursive algorithms whose running time ofcomputing satisfies the recurrence equation (8).
Theorem 9 Let and . Fix and with and for all and . Let be the mapping defined by
Then the following assertions hold:
-
(1)
has a unique fixed point .
-
(2)
.
-
(3)
If such that , then .
-
(4)
If , then provided that and .
Proof The completeness of the Baire partial quasi-metric space shows that the quasi-metric space is bicomplete. Moreover, by Lemma 7, we see that the set is closed in . Thus the quasi-metric space is bicomplete. Whence we deduce that the partial quasi-metricspace is complete. Furthermore, it is a straightforward computationto check that the mapping obeys the following inequality:
for all . It follows, by Theorem 4, that has a unique fixed point with . Hence . So we have proved statements (1) and (2).
Now assume the existence of such that . It follows, by construction of , that . Since we obtain . Hence, by assertion (1) in statement of Lemma 8, wefind that . Whence we deduce that and, hence, that . This proves statement (3).
Finally, assume the existence of such that . It follows that . Since we deduce that . Hence, by assertion (2) in statement of Lemma 8, wefind that . Whence we deduce that . This proves statement (4). □
We must emphasize that taking and in statement of Theorem 9 we retrieve, as a particularcase, Theorem 5. Moreover, setting and for any with in statement of Theorem 9 we obtain the followingcorollary.
Corollary 10 Let . Fix and with , and for all and . Let be the subset of given by and let be the mapping defined by
Then the following assertions hold:
-
(1)
has a unique fixed point .
-
(2)
.
-
(3)
If such that , then .
-
(4)
If , then provided that and .
Next we want to emphasize that the Divide and Conquer recurrence equation (2) can betransformed into the recurrence equation
where and for all (recall that with and ).
Therefore Corollary 10, and with it Theorem 9, retrieve as a particular caseTheorem 6 given in [4], which was obtained with the aim of analyzing the asymptotic complexity ofthose algorithms with running time of computing satisfying the recurrence equation (2) bymeans of fixed-point arguments based on the Baire partial quasi-metric space. In thisdirection, Theorem 9 allows us to unify Theorem 5 and Theorem 6 and, hence,to obtain a unique fixed-point technique, via the Baire partial quasi-metric space, forthe mathematical foundation of the asymptotic complexity analysis of those algorithmswhose running time leads in a natural way to recurrence equations of the type of equations(2), (6), and (16), where
with , , and such that for all .
Notice that the recurrence equation (9) associated to Hanoi is a concrete case ofequation (16). Besides, celebrated examples of algorithms whose running time of computinglead to the recurrence equations (2) and (16) are, for instance, Mergesort and Quicksort(for more details see [5] and [14]).
3.2 The application to asymptotic complexity analysis
Notice that Theorem 9 yields a new fixed-point technique to analyze the complexityclass of all those algorithms whose running time of computing satisfies the recurrenceequation (8). Indeed, we associate to the recurrence equation (8) the functional defined by
Then Theorem 9 provides, in a very easy way without involving arduous computations,the promised asymptotic complexity technique, Theorem 11, to determine the asymptoticcomplexity (upper and lower) bounds, and thus the complexity class, of the running time ofthose algorithms under study.
Theorem 11 A recurrence equation of the form (8) has a unique solution . Moreover, if there exist such that and , then . Furthermore, provided that there exist and in such a way that the preceding functions g, h satisfy and for all .
Proof Let be the fixed point of the mapping ensured by Theorem 9. Now, define by for all . Then we immediately see that is the unique solution to the recurrence equation (8). So can be identified with the running time of computing of arecursive algorithm satisfying the recurrence equation (8), say . Of course, for all .
Next assume that there exists such that . Then we identify such a function with a word which is defined by for all . It is obvious that . It follows, by Theorem 9, that . Hence we have showed that or, equivalently, that .
Now suppose that there exists such that . Then we identify such a function with a word which is defined by for all . Clearly and . By Theorem 9 we obtain . Whence we deduce that and, hence, that or, equivalently, that .
Finally, assume that there exist and such that the function satisfy and for all . Since and we have . It follows that . Consequently . Thus . □
Observe that, although Theorem 5 can be obtained from Theorem 9, the lattergives a few more information about the running time of computing under consideration thanthe former. This is due to the fact that the assertion (4) in statement of Theorem 9allows to determine the lower asymptotic complexity bound for algorithms whose runningtime obeys equation (6) while that Theorem 5 does not allow one to do this.Consequently, the version of Theorem 5 retrieved from Theorem 9 improvesTheorem 5. So the new fixed-point result is clearly a non-trivial extension of theold one.
Furthermore, it must be stressed that a first attempt to apply fixed-point techniquesbased on the use of words to complexity analysis of algorithms was made in [17] by means of the so-called Baire balanced quasi-metric. However, theaforementioned quasi-metric fixed-point technique was only able to provide the existenceand uniqueness of solution to recurrence equations and not the complexity class. So, insome sense, our new technique improves those given in [17], since Theorem 9 allows to obtain the asymptotic complexity class of thesolution to a recurrence equation associated to an algorithm and, thus, the complexityclass of its running time of computing.
In order to help the reader to glimpse the utility of Theorem 11, and with it alsoof Theorem 9, we end the paper showing that, like the Schellekens approach, thedeveloped theory is helpful in providing the asymptotic complexity class of the recursivealgorithms whose running time satisfies the recurrence equation (8). In particular, weapply Theorem 11 to the analysis of Hanoi and Fibonacci, retrieving their well-knownasymptotic complexity class [14].
Hanoi As mentioned before, the running time of computing of Hanoi matches up withthe solution, under the uniform cost criterion assumption (see [14]), to the recurrence equation (9). Of course, such a recurrence equation can beretrieved from equation (8) as a particular case when we put , , and for all . Consider the functional associated with equation (9) andgiven by equation (17) as follows:
for all . Then Theorem 11 yields the existence and uniqueness of thesolution (in ), which obviously represents the running time of computing ofHanoi, to the above recurrence equation.
It is a straightforward computation to check that for any if and only if and for all with . Thus, by Theorem 11, we deduce that, where
Moreover, it is not hard to check that for any if and only if and for all with . Thus, by Theorem 11, we deduce that, where
Accordingly, by Theorem 11, we obtain with g and h given by equations (19) and(20), respectively. Since we conclude, by Theorem 11, that . Therefore we have proved the following result.
Corollary 12 The complexity class of the running time of computing of Hanoi is .
Fibonacci As we have exposed above, the running time of computing of Fibonacci isthe solution to the recurrence equation (10). Clearly, such a recurrence equation can beretrieved from equation (8) as a particular case when we put , , , and for all . Consider the functional associated with equation (10) andgiven by equation (17) as follows:
for all . Then Theorem 11 yields the existence and uniqueness of thesolution (in ), which obviously represents the running time of computing ofFibonacci, to the above recurrence equation.
In order to guess the asymptotic bounds we fix and and define the function by
In what follows we denote the value by ϕ. It is a straightforward computation tocheck that if and only if and . Then, by Theorem 11, for all and . Hence, taking , we immediately have .
Moreover, it is not hard to check that if and only if for all . It follows, by Theorem 11, that for all and all . Hence, taking , we obtain .
Consequently, by Theorem 11, we obtain for all . Therefore we have proved the following result.
Corollary 13 The running time of computing of Fibonacci belongs to the complexity class .
Observe that the fact that the running time of computing is in guarantees that any other function, different from, chosen to determine the complexity class of would not be able to provide the suitable lower and upperasymptotic bounds at the same time.
References
Matthews SG: Partial metric topology. Ann. N.Y. Acad. Sci. 1994, 728: 183–197. 10.1111/j.1749-6632.1994.tb44144.x
Matthews SG: An extensional treatment of lazy data flow deadlock. Theor. Comput. Sci. 1995, 151: 195–205. 10.1016/0304-3975(95)00051-W
Schellekens MP: The Smyth completion: a common foundation for denotational semantics and complexityanalysis. Electron. Notes Theor. Comput. Sci. 1995, 1: 211–232.
Cerdà-Uguet MA, Schellekens MP, Valero O: The Baire partial quasimetric space: a mathematical tool for the asymptotic complexityanalysis in computer science. Theory Comput. Syst. 2012, 50: 387–399. 10.1007/s00224-010-9310-7
Brassard G, Bratley P: Algorithms: Theory and Practice. Prentice Hall, New Jersey; 1988.
Künzi HPA: Nonsymmetric distances and their associated topologies: about the origins of basicideas in the area of asymmetric topology. 3. In Handbook of the History of General Topology. Edited by: Aull CE, Lowen R. Kluwer Academic, Dordrecht; 2001:853–968.
Romaguera S, Schellekens MP: Quasi-metric properties of complexity spaces. Topol. Appl. 1999, 98: 311–322. 10.1016/S0166-8641(98)00102-3
Scott DS: Outline of a mathematical theory of computation. Proc. 4th Annual Princeton Conference on Information Sciences and Systems 1970, 169–176.
Oltra S, Romaguera S, Sánchez-Pérez EA: Bicompleting weightable quasi-metric spaces and partial metric spaces. Rend. Circ. Mat. Palermo 2002, 51: 151–162. 10.1007/BF02871458
Alghamdi MA, Shahzad N, Valero O: Fixed point theorems in generalized metric spaces with applications to computerscience. Fixed Point Theory Appl. 2013., 2013: Article ID 118
Künzi HPA, Pajooshesh H, Schellekens MP: Partial quasi-metrics. Theor. Comput. Sci. 2006, 365: 237–246. 10.1016/j.tcs.2006.07.050
Karapinar E, Erhan IM, Öztürk A: Fixed point theorems on quasi-partial metric spaces. Math. Comput. Model. 2013, 57: 2442–2448. 10.1016/j.mcm.2012.06.036
Shoaib A, Arshad M, Ahmad J: Fixed point results of locally contractive mappings in ordered quasi-partial metricspaces. Sci. World J. 2013., 2013: Article ID 194897
Cull P, Flahive M, Robson R: Difference Equations: From Rabbits to Chaos. Springer, New York; 2005.
Romaguera S, Tirado P, Valero O: New results on mathematical foundations of asymptotic complexity analysis of algorithmsvia complexity spaces. Int. J. Comput. Math. 2012, 89: 1728–1741. 10.1080/00207160.2012.659246
Romaguera S, Valero O: A common mathematical framework for asymptotic complexity analysis and denotationalsemantics for recursive programs based on complexity spaces. 1. In Semantics-Advances in Theories and Mathematical Models. Edited by: Afzal MT. InTech, Rijeka; 2012:99–120.
Rodríguez-López J, Romaguera S, Valero O: Denotational semantics for programming languages, balanced quasi-metrics and fixedpoints. Int. J. Comput. Math. 2008, 85: 623–630. 10.1080/00207160701210653
Acknowledgements
This work was funded by the Deanship of Scientific Research (DSR), King AbdulazizUniversity, Jeddah, under grant No. 363-002-D1434. The authors, therefore acknowledge withthanks DSR for technical and financial support.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally and took part in every discussion. All authors read andapproved the final manuscript.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Alghamdi, M.A., Shahzad, N. & Valero, O. New results on the Baire partial quasi-metric space, fixed point theory and asymptoticcomplexity analysis for recursive programs. Fixed Point Theory Appl 2014, 14 (2014). https://doi.org/10.1186/1687-1812-2014-14
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/1687-1812-2014-14