We also present a tableau calculus for deciding ALC+Tmin entailment that allows to give a complexity upper bound for the logic, namely that query entailment is in co-NExpNP.
Finally, we apply, in the spirit of [6], the developed theory to complexity analysis by means of determining the asymptotic upper bound of the complexity of those algorithms whose running time of computing is the solution to a special type of recurrence equation.
Finally, the applicability of the exposed results is illustrated providing a methodology to determine the asymptotic upper bound of the complexity of those algorithms whose running time of computing is the solution to a special type of recurrence equation.
In particular, he introduced a method, based on a fixed point theorem for functionals defined on the complexity space into itself, to provide the asymptotic upper bound of those algorithms whose running time of computing satisfies a recurrence equation of Divide and Conquer type.
Therefore, using the big-O notation, the time complexity of an algorithm is usually expressed in an asymptotic upper bound on the number of operations[20].
So, Schellekens proved that Mergesort running time (average case behavior) belongs to the asymptotic complexity class Θ ( n log 2 ( n ) ), but the fixed point technique was used only to provide the asymptotic upper bound.
Although we assume that the reader is familiar with the basic notions from asymptotic complexity analysis (for a full treatment we refer the reader to [16]), let us recall that g is an asymptotic upper bound of f, denoted by (fin mathcal{O}(g)), provided that there exist (n_{0}inmathbb{N}) and (cinmathbb{R}_{0}^) such that (f(n leq cg(n)) for all (ninmathbb{N}) with (ngeq n_{0}).
Hence the complexity function g 1 2, or equivalently O ( n log 2 ( n ) ), gives an asymptotic upper bound of the running time of computing of the aforenamed algorithm.
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).
for all f ∈ C c. Next we provide the asymptotic upper bound of f T H.
for all f ∈ C c. Next we provide the asymptotic upper bound of f T Q.
