Research Article

# Quicksort Algorithms: Application of Fixed Point Theorem in Probabilistic Quasi-Metric Spaces at Domain of Words

S. Shakeri, M. Jalili, R. Saadati, S.M. Vaezpour and Lj. Ciric

ABSTRACT

This research applied on a probabilistic quasi-metric version of a fixed point theorem to obtain the existence of solution for a recurrence equation associated to the analysis of Quicksort algorithms. Actually, we will establish ther results in the more general framework of probabilistic quasi-metric spaces because, in this context, the measurement of the distance from a word x to another word y, automatically indicates if x is a prefix of y or not, while the Baire metric does not provide this information. Finally, will be applied our methods to prove the existence (and uniqueness) of solution for some recurrence equations associated to the asymptotic complexity analysis of Quicksort algorithms and Divide and Conquer algorithms, respectively.

 Services Related Articles in ASCI Search in Google Scholar View Citation Report Citation

 How to cite this article: S. Shakeri, M. Jalili, R. Saadati, S.M. Vaezpour and Lj. Ciric, 2009. Quicksort Algorithms: Application of Fixed Point Theorem in Probabilistic Quasi-Metric Spaces at Domain of Words. Journal of Applied Sciences, 9: 397-400. DOI: 10.3923/jas.2009.397.400 URL: https://scialert.net/abstract/?doi=jas.2009.397.400

INTRODUCTION

Menger (1942) introduced the notion of a probabilistic metric space and since then the theory of probabilistic metric spaces has developed in many directions (Schweizer and Sklar, 1983). The idea of Menger (1942) was to use distribution functions instead of nonnegative real numbers as values of the metric. The notion of a probabilistic metric space corresponds to situations when we do not know exactly the distance between two points, but is knew probabilities of possible values of this distance. A probabilistic generalization of metric spaces appears to be interest in the investigation of physical quantities and physiological thresholds. It is also of fundamental importance in probabilistic functional analysis and random differential equations (Chang et al., 2001). Throughout this study, the space of all probability distribution functions (briefly, df`s) is denoted by:

 Δ+ = {F: R∪(-∞, +∞)→[0, 1]: F(0) = 0 and F(+∞) = 1}

where, F is left continuous and non decreasing on R.

Also the subset is the set:

 D+ = {FεΔ+: l-F (+∞) = 1}

where, l-f (x) denotes the left limit of the function f at the point x, l-f (x) = limt→x f (t) The space Δ+ is partially ordered by the usual point-wise ordering of functions, i.e., F≤G if and only if F(t) ≤G (t) for all t in R. The maximal element for Δ+ in this order is the df given by:

Definition 1: A mapping T: [0, 1]x[0,1→[0,1] is a continuous t-norm if T satisfies the following conditions:

 • T is commutative and associative • T is continuous • T (a, 1) = a for all aε(0, 1) • T (a, b)≤T(c, d) whenever a≤c and b≤d and a, b, c, d ε[0, 1]

Two typical examples of continuous t-norm are T (a, b) = ab and T(a, b) = min (a, b). Now t-norms are recursively defined by T1 = T and Tn (x1, …, xn+1) = T (Tn-1 (x1, .., xn), xn+1) for n≤2 and xi ε[0, 1] for all I ε{1, 2, .., n+1}

Definition 2: The t-norm T is Hadzic type if for given εε(0, 1) there is δε(0, 1) such that:

 Tm (1-δ, …, 1-δ)>1-ε, mεN

A typical example of such t-norms is T (a, b) = min (a, b).

Definition 3: A Menger Probabilistic Quasi-Metric space (briefly, Menger PQM space) is a triple (X, F, T), where, X is a nonempty set, T is a continuous t-norm and F is a mapping from XxX into D+ such that, if Fx,y denotes the value of F at the pair (x, y), the following conditions hold: for all x, y, z ε X, (PM1) Fx,y (t) = ε0 (t) for all t > 0 if and only if x = y; (PM2) Fx,y (t+s)≥T (Fx, z (t), Fz, y (s)) for all x, y, z εX and t, s>0.

If (X, F, T) is a Menger PQM space then (X, F-1, T) is a Menger PQM space, where, Fx,y-1 (t) = Fx,y (t). Moreover, if we denote by Fi the probabilistic quasi-metric in XxXx (0, ∞) given by:

 Fix,y (t) = T (Fx,y (t), F-1x,y (t))

then (X, Fi, T) is a Menger PQM space.

Definition 4: Let (X, F, T) be a Menger PM-space:

 • A sequence {xn} in X is said to be convergent to x in X if, for every α>0 and β>0, there exists positive integer N such that Fxn,x (α)>1-β whenever n≥N. • A sequence {xn} in X is called Cauchy sequence if, for every α>0 and β>0, there exists positive integer N such that Fxn,xm(α)>1-β whenever, m≥N • A Menger PM-space (X, F, T) is said to be complete if and only if every Cauchy sequence in X is convergent to a point in X

Definition 5: A sequence {xn} in a Menger PM-space (X, F, T) is called a G-Cauchy sequence if limn→4 Fxn,xn+P(t) = 1 for each t>0 and pεN. A Menger PM-space is said to be G-complete if and only if every G-Cauchy sequence is convergent.

Definition 6: A sequence {xn} in a Menger PQM-space (X, F, T) is G-Cauchy if it is G-Cauchy in the Menger PQM-space (X, Fi, T).

Definition 7: A a Menger PQM-space (X, F, T) is called G-bicomplete if the a Menger PQM-space (X, Fi, T) is G-complete. In this case, we say that F is a G-bicomplete Menger PQM-space on X.

Definition 8: Let (X, F, T) be a Menger PQM-space. For each p in X and α>0, the strong α-neighborhood of p is the set NP (α) = (qεX: Fp, q (α)>1-α) and the strong neighborhood system for X is the union ∪pεXwhere, {Np (α): α>0}.

The strong neighborhood system for X determines a Hausdorff topology for X.

Example 1: Let (X, d) be a quasi metric space. Let

then (X, F, min) is a Menger PQM-space.

THE BANACH FIXED POINT THEOREM IN MENGER PQM-SPACE

A B-contraction on a Menger PQM-space (X, F, T) is a self mapping f on X such that there is a constant k ε (0, 1) satisfying:

The following theorem is an extension of Sehgal and Bharucha-Reid`s theorem (1972).

Theorem 1: Let (X, F, T) be a G-bicomplete Menger PQM-space. Then every B-contraction on X has a unique fixed point.

G-BICOMPLETENESS IN NON-ARCHIMEDIAN PQM-SPACE

Definition 9: If in a PQM-space (X, F, T) the triangle inequality, (PM2) of Definition 3, is replaced by:

 Fx,y (t)≥T (Fx,z (t), Fz,y (t))

for all x, y, z εX and t>0 is called a non-Archimedian PQM-space.

Example 2: Let (X, d) be a quasi metric space. It is immediate to show that (X, d) is a non-Archimedian quasi metric space if and only if (X, Fd, min) is a non-Archimedian PQM-space.

Theorem 2: Each G-Cauchy sequence in a non-Archimedian PQM-space (X, F, T), where, T is Hadzic type, is Cauchy sequence.

Proof: Since T is Hadzic type, for given ε ε (0, 1) there is δε (0, 1) such that Tm (1-δ, …, 1-δ) >1-ε, mεN.

Let (xn) be a G-Cauchy sequence in the non-Archimedian PQM-space (X, F, T). Fix εε (0, 1) and t>0 and consider n0 such that for all n≥n0. Then, for all n≥n0 and j>0 we have:

This shows that (xn) be a Cauchy sequence in (X, F, T).

Theorem 3: Each bicomplete non-Archimedian PQM-space (X, F, T), where, T is Hadzic type, is G-complete.

Proof: Let {xn} be a G-Cauchy sequence in the non-Archimedian PQM-space. By Theorem 3, (xn) is a Cauchy sequence in (X, F, T). Then, there exists xεX such that limn→4 Fix,xn (t) = 1 for all t>0. Hence, (X, Fi, T) is G-complete, i.e., (X, F, T) is G-bicomplete.

APPLICATIONS TO THE DOMAIN OF WORDS

Let ∑ be a nonempty alphabet. Let ∑ be the set of all finite and infinite sequence (words) over ∑, where is adopted the convention that the empty sequence φ is an element of ∑.

Denote by ⊆ the prefix order on ∑, i.e., x⊆⇔x is a prefix of y. For each xε∑ denote by l (x) the length of x. Then l(x)ε(1, ∞) whenever ≠ φ and l(φ) = 0. For each x, y ε∑ let xII y be the common prefix of x and y. Thus, the function d defined on∑H∑ by:

 d⊆ (x, y) = 0 if x⊆y
 d⊆ (x, y) = 2-l(xII y), otherwise,

is a quasi metric on ∑. It adopt the convention that 2-4 = 0 (for more details see De Bakker et al. (1998)).

Let be defined as:

 • (0) = 0, for all x, y ε ∑∞ • (t) = ε0 if x is a prefix of y and t>0 • (t) = 1-2-l(xII y) if x is not a prefix of y and tε(0,1) • (t) = ε0(t) if x is not a prefix of y and t>1.

Theorem 4: (∑, Fd⊆1, min) is a bicomplete non- Archimedian PQM-space.

Proof: (Romaguera et al., 2007).

Let be defined as:

If t = 0, for all x, yε ∑,

if t > 0, if x is not a prefix of y, if t>0, if x is a prefix of y, where, k>1.

Theorem 5: (∑, Fd⊆, min) is a bicomplete non-Archimedian PQM-space. Next, is applied Theorem 1 to the complexity analysis of Quicksort algorithms. The following recurrence equation (Romaguera et al., 2007):

is obtained in the average case analysis of Quicksort algorithms. Consider as an alphabet ∑ the set of nonnegative real numbers, i.e., ∑ = (0, ∞). Now is associated to T the functional Φ: ∑6∑ given by:

for all n≥2 (if xε ∑ has length, n<∞ is wrote x: = xSUB>1x2..xn and if x is an infinite word is wrote x:= x1x2…).

Now, is showed that Φ is a B-contractive mapping on the bicomplete non-Archimedean. PQM-space (∑, Fd⊆, min) with contraction constant 1/k.

By construction, l (Φ (x)) = l (x)+1 for all x, yε∑ (in particular, l (Φ (x)) = ∞ whenever l (x) = ∞). Furthermore, it is clear that x⊆y if and only if Φ (x) ⊆Φ(y) and consequently, Φ(xII y)⊆Φ(x)II Φ(y) for all x, yε∑. Hence l (Φ (xII y)) ≤l (Φ (x) II Φ (y)) for all x, y ε∑.

From the preceding observations is deduced that if x is a prefix of y, then

and if x is not a prefix of y, then

for all t>0. Similarly,

Therefore, Φ is a B-contraction on (∑, Fd⊆, min) with contraction constant 1/k. By Theorem 1, Φ has a unique fixed point z = z1z2…, which is the unique solution to the recurrence equation T, i.e., z1 = 0 and

for all n≥2.

REFERENCES

1:  De Bakker, J.W. and E.P. De Vink, 1998. Denotational models for programming language: Application of banach fixed point theorem. Topol. Appl., 85: 35-52.

2:  Chang, S.S., Y.J. Cho and S.M. Kang, 2001. Nonlinear Operator Theory in Probabilistic Metric Spaces. 1st Edn., Nova Science Publishers Inc., New York, USA., ISBN: 1-56072-980-5

3:  Menger, K., 1942. Statistical metrics. Proc. Nat. Acad. Sci., 28: 535-537.