# A New Asymptotic Notation: Weak Theta

Authors: Andrei-Horia Mogoş; Bianca Mogoş; Adina Magda Florea
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Algorithms represent one of the fundamental issues in computer science, while asymptotic notations are widely accepted as the main tool for estimating the complexity of algorithms. Over the years a certain number of asymptotic notations have been proposed. Each of these notations is based on the comparison of various complexity functions with a given complexity function. In this paper, we define a new asymptotic notation, called “Weak Theta,” that uses the comparison of various complexity functions with two given complexity functions. Weak Theta notation is especially useful in characterizing complexity functions whose behaviour is hard to be approximated using a single complexity function. In addition, in order to highlight the main particularities of Weak Theta, we propose and prove several theoretical results: properties of Weak Theta, criteria for comparing two complexity functions, and properties of a new set of complexity functions (also defined in the paper) based on Weak Theta. Furthermore, to illustrate the usefulness of our notation, we discuss an application of Weak Theta in artificial intelligence.


---

## Body

## 1. Introduction

Computational complexity [1–6] is a very popular research area in computer science that covers algorithm design [3, 4], algorithm complexity [3, 4], asymptotic notations [3, 7–9], complexity recurrences [3, 10, 11], classes of problems and NP-completeness [12, 13], and heuristics and approximation algorithms [13, 14].Tools from computational complexity are intensively used in various research areas such as computer networks [15], operating systems [16], parallel and distributed computing [17], and artificial intelligence [18, 19]. Artificial intelligence is particularly linked with computational complexity; see swarm intelligence [20–25], multiagent systems [26–28], machine learning [29, 30], and semantic web services [31, 32].Algorithms represent one of the most important issues in computer science, while asymptotic notations are considered to be the main tool for estimating the complexity of algorithms. Several asymptotic notations have been proposed in the literature. They are all based on the comparison of various complexity functions with a given complexity function. Consequently, the main idea is to choose a complexity function and then to see what is the relation between this function and other complexity functions. Some of these asymptotic notations provide relations that are too general, while others offer relations that are too specific and therefore not applicable for all the cases.In this paper, we propose a new asymptotic notation that aims to offer a solution for the problem discussed above. It proposes the use of two given complexity functions to construct the set of all complexity functions that can be caught between these two given functions. The main advantage of our asymptotic notation is the fact that it can be used to describe the behaviour of a wide set of complexity functions (some of them hard to be approximated using a single complexity function). In this paper, we also propose and prove several properties that characterize this new asymptotic notation and outline its importance in the field of computational complexity.The paper is organized as follows. Section2 contains an overview on the asymptotic notations proposed in the literature. In Section 3, we define an asymptotic notation, called “Weak Theta,” we provide a motivation for the need of this notation, and we discuss an application of “Weak Theta” in artificial intelligence. In the end of this section, we also present a brief description of the main symbols used in the paper. In Section 4, we propose several relations between “Weak Theta” and other asymptotic notations. In Section 5, we develop some properties of “Weak Theta” related to membership, inclusion, intersection, and union. In Section 6, we discuss several criteria concerning the comparison of two complexity functions. In Section 7, we define the set of complexity functions comparable with two given complexity functions and we propose several properties of this new set of functions. Section 8 contains the conclusions of the paper.


## 2. Related Work

In this section, we present several asymptotic notations proposed in the literature.Definition 1 (see, e.g., [3, 6, 7]).
A complexity function is a functionf
:
N
∗
→
R
+
∗, where N
∗ is the set of positive integers and R
+
∗ is the set of positive real numbers. One denotes by F the set of complexity functions, F
=
{
f
:
N
∗
→
R
+
∗
}.Remark 2.
In this paper, a functionf
∈
F will be denoted by f
(
n
) whenever this function is in relation with a complexity class that depends on a complexity function of the argument n (e.g., f
∈
F, but f
(
n
)
∈
Θ
(
f
(
n
)
)).Definition 3 (see, e.g., [3, 4, 6, 7, 33–36]).
Letg
∈
F, an arbitrary fixed complexity function. The main asymptotic notations used in the literature are defined as follows:(1)
Θ
g
n
=
f
∈
F
∣
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
kklk
such
that
c
1
·
g
n
≤
f
n
≤
c
2
·
g
(
n
)
,
kklk
∀
n
≥
n
0
,
O
g
n
=
f
∈
F
∣
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
kklk
such
that
f
(
n
)
≤
c
·
g
(
n
)
,
kklk
∀
n
≥
n
0
,
Ω
g
n
=
f
∈
F
∣
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
kkkl
such
that
c
·
g
(
n
)
≤
f
(
n
)
,
k
k
k
l
∀
n
≥
n
0
,
o
g
n
=
f
∈
F
∣
∀
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
kkkl
such
that
f
(
n
)
<
c
·
g
(
n
)
,
kkkl
∀
n
≥
n
0
,
ω
g
n
=
f
∈
F
∣
∀
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
kkkl
such
that
c
·
g
(
n
)
<
f
(
n
)
,
kkkl
∀
n
≥
n
0
.Proposition 4 (see, e.g., [3, 6]).
One has the following.(a)
Reflexivity. Letf
∈
F. Then f
(
n
)
∈
Θ
(
f
(
n
)
), f
(
n
)
∈
O
(
f
(
n
)
), and f
(
n
)
∈
Ω
(
f
(
n
)
).
(b)
Transitivity. Letf
,
g
,
h
∈
F. Then,
(b1)
iff
(
n
)
∈
Θ
(
g
(
n
)
) and g
(
n
)
∈
Θ
(
h
(
n
)
) then f
(
n
)
∈
Θ
(
h
(
n
)
);
(b2)
iff
(
n
)
∈
O
(
g
(
n
)
) and g
(
n
)
∈
O
(
h
(
n
)
) then f
(
n
)
∈
O
(
h
(
n
)
);
(b3)
iff
(
n
)
∈
Ω
(
g
(
n
)
) and g
(
n
)
∈
Ω
(
h
(
n
)
) then f
(
n
)
∈
Ω
(
h
(
n
)
);
(b4)
iff
(
n
)
∈
o
(
g
(
n
)
) and g
(
n
)
∈
o
(
h
(
n
)
) then f
(
n
)
∈
o
(
h
(
n
)
);
(b5)
iff
(
n
)
∈
ω
(
g
(
n
)
) and g
(
n
)
∈
ω
(
h
(
n
)
) then f
(
n
)
∈
ω
(
h
(
n
)
).
(c)
Symmetry. Letf
,
g
∈
F. If f
(
n
)
∈
Θ
(
g
(
n
)
) then g
(
n
)
∈
Θ
(
f
(
n
)
).
(d)
Transpose Symmetry. Let bef
,
g
∈
F. Then,
(d1)
f
(
n
)
∈
O
(
g
(
n
)
) if and only if g
(
n
)
∈
Ω
(
f
(
n
)
);
(d2)
f
(
n
)
∈
o
(
g
(
n
)
) if and only if g
(
n
)
∈
ω
(
f
(
n
)
).
(e)
Projection. Letf
,
g
∈
F. Then f
(
n
)
∈
Θ
(
g
(
n
)
) if and only if f
(
n
)
∈
O
(
g
(
n
)
) and f
(
n
)
∈
Ω
(
g
(
n
)
).Definition 5 (see [7]).
Letg
∈
F. The set of all complexity functions comparable with g
(
n
) is defined as follows:(2)
C
g
n
=
Θ
g
n
∪
O
g
n
∪
Ω
g
n
∪
o
(
g
(
n
)
)
∪
ω
(
g
(
n
)
)
.Definition 6 (see [7]).
Letg
∈
F. The asymptotic notations o
Θ
(
g
(
n
)
) and Θ
ω are defined as follows:(3)
o
Θ
g
n
=
O
g
n
∖
o
g
n
∪
Θ
g
n
,
Θ
ω
g
n
=
Ω
g
n
∖
Θ
g
n
∪
ω
g
n
.Proposition 7 (see [7]).
Letg
∈
F. Then (a)
O
(
g
(
n
)
)
=
o
(
g
(
n
)
)
∪
o
Θ
(
g
(
n
)
)
∪
Θ
(
g
(
n
)
);
(b)
Ω
(
g
(
n
)
)
=
Θ
(
g
(
n
)
)
∪
Θ
ω
(
g
(
n
)
)
∪
ω
(
g
(
n
)
).Proposition 8 (see [7]).
Letg
∈
F. Then,(a)
C
(
g
(
n
)
)
=
o
(
g
(
n
)
)
∪
o
Θ
(
g
(
n
)
)
∪
Θ
(
g
(
n
)
)
∪
Θ
ω
(
g
(
n
)
)
∪
ω
(
g
(
n
)
);
(b)
o
(
g
(
n
)
), o
Θ
(
g
(
n
)
), Θ
(
g
(
n
)
), Θ
ω
(
g
(
n
)
), and ω
(
g
(
n
)
) are pairwise disjoint;
(c)
C
(
g
(
n
)
)
=
O
(
g
(
n
)
)
∪
Ω
(
g
(
n
)
).
Other important asymptotic notations used in the literature are the following: softO [3, 8], soft Θ [36, 37], Ω infinity [3, 9], ~ [35, 38], and almost [35].


## 3. Weak Theta

In this section, we propose a new asymptotic notation called “Weak Theta,” we present some motivation for using this notation, and we discuss an application of “Weak Theta” in artificial intelligence. In the end of the section we briefly describe the main symbols used in the paper.


### 3.1. Definition of Weak Theta

Definition 9.
Letg
1
,
g
2
∈
F. One defines the asymptotic notation Weak Theta, denoted by Θ
̿, as follows:(4)
Θ
̿
g
1
n
,
g
2
n
=
f
∈
F
∣
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
kkklkl
such
that
c
1
·
g
1
n
≤
f
n
≤
c
2
·
g
2
n
,
kkkkll
∀
n
≥
n
0
.Remark 10.
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
) represents the set of all complexity functions that are bounded by the functions c
1
·
g
1
(
n
) and c
2
·
g
2
(
n
) for sufficiently large n.Proposition 11.
Letg
1
,
g
2
∈
F. Then(a)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅ if and only if g
1
(
n
)
∈
O
(
g
2
(
n
)
);
(b)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅ if and only if g
2
(
n
)
∈
Ω
(
g
1
(
n
)
).Proof.
(a) “⇒” Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). Then,(5)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
n
≤
f
n
≤
c
2
·
g
2
n
,
∀
n
≥
n
0
.It follows that(6)
∃
c
′
=
c
2
c
1
∈
R
+
∗
,
∃
n
0
′
=
n
0
∈
N
∗
such
that
g
1
n
≤
c
′
·
g
2
n
,
∀
n
≥
n
0
′
.Consequently,(7)
g
1
(
n
)
∈
O
(
g
2
(
n
)
)
.
“⇐” Consider that g
1
(
n
)
∈
O
(
g
2
(
n
)
); it follows that(8)
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
g
1
n
≤
c
·
g
2
n
,
∀
n
≥
n
0
.
From (8), we obtain(9)
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
1
·
g
1
n
≤
g
1
n
≤
c
·
g
2
n
,
∀
n
≥
n
0
.
So, we have(10)
∃
c
1
′
=
1
,
c
2
′
=
c
∈
R
+
∗
,
∃
n
0
′
=
n
0
∈
N
∗
such
that
c
1
′
·
g
1
n
≤
g
1
n
≤
c
2
′
·
g
2
n
,
∀
n
≥
n
0
′
.
Consequently,(11)
g
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.
(b) The result follows from (a) using the relation(12)
g
1
(
n
)
∈
O
g
2
n
iff
g
2
(
n
)
∈
Ω
(
g
1
(
n
)
)
.Remark 12.
In all situations in which a proposition or a theorem has as a hypothesis a relation of the formg
1
(
n
)
∈
O
(
g
2
(
n
)
), one implicitly understands that Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅.


### 3.2. Motivation

(a) The first use of our notation is for describing complexity functions with complex behaviour (i.e., functions difficult to be approximated by a single elementary complexity function). As an example, letf
∈
F with the form(13)
f
(
n
)
=
n
2
,
n
=
3
k
,
n
lg
n
,
n
=
3
k
+
1
,
n
,
n
=
3
k
+
2
.If we use the asymptotic notations from Definition3, we may obtain (14)
f
(
n
)
∈
O
(
n
2
)or(15)
f
(
n
)
∈
Ω
(
n
)which are too general descriptions of the behavior of f
(
n
), while the use of Θ is not appropriate.If we use the new asymptotic notation proposed in Definition9, then we obtain(16)
f
(
n
)
∈
Θ
̿
(
n
,
n
2
)
.(b) Usually, the best case, the worst case, and the average case of the running time of an algorithm are described by functions with different behaviours. Also, for all algorithms, the average case is situated between the best case and the worst case. For example, assume that for an algorithmA the best case is represented by f
1
(
n
)
=
n
2
lg
n
+
n and the worst case is represented by f
2
(
n
)
=
n
3
+
n
2.UsingΘ, we obtain that f
1
(
n
)
∈
Θ
(
n
2
lg
n
) and f
2
(
n
)
∈
Θ
(
n
3
). This is a valid description of the two cases of the algorithm, but we need two complexity classes (Θ
(
n
2
lg
n
) and Θ
(
n
3
)) for this analysis.If we useΘ
̿, only one complexity class is necessary. The running time of the algorithm A is fully described by Θ
̿
(
n
2
lg
n
,
n
3
).


### 3.3. An Application of Weak Theta in Artificial Intelligence

In this subsection, we propose an artificial intelligence based solution for the following problem denoted byP
1. “Let SP
=
{
p
1
,
p
2
,
…
,
p
k
} be a set of software programs and P
2 a given problem. Each program p
i, i
=
1
,
k
¯, solves the problem P
2. We make the following assumptions: (
1
) each program p
i, i
=
1
,
k
¯, terminates for each valid input; (
2
) for all programs p
i, i
=
1
,
k
¯, the inputs have the same form; (
3
) the codes of the programs are not available. One asks to find the fastest program(s) from the set SP.”The problemP
1 can be seen as an unsupervised classification problem that can be solved in terms of “Weak Theta.” In this framework, we propose an algorithm that aims to solve the problem P
1. This algorithm uses for the first two steps a simple and common idea for estimating the running time of a software program: “choose several inputs for the program; for each input measure the corresponding running time and then, using this information, find the function that best estimates the running time of the program.”The algorithm can be described as follows.Step 1.
Consider a set of inputs{
input
1
,
input
2
,
…
,
input
q
} of sizes {
s
1
,
s
2
,
…
,
s
q
} (where s
j is the size of input input
j). We run each program p
i, i
=
1
,
k
¯, for all inputs and we obtain the corresponding running times {
t
1
i
,
t
2
i
,
…
,
t
q
i
}. In the end, for each program p
i, i
=
1
,
k
¯, we will have a set of pairs S
i
=
{
(
s
1
,
t
1
i
)
,
(
s
2
,
t
2
i
)
,
…
,
(
s
q
,
t
q
i
)
}.Step 2.
For each programp
i, i
=
1
,
k
¯, we use the data S
i for obtaining a complexity function g
i that best approximates the running time of the program. For this step we may use estimation techniques.Step 3.
First, we choose a set of complexity functions{
f
1
,
f
2
,
…
,
f
r
} such that f
j
(
n
)
∈
O
(
f
j
+
1
(
n
)
), for all j
=
1
,
r
-
1
¯; from Proposition 11, we have Θ
̿
(
f
j
(
n
)
,
f
j
+
1
(
n
)
)
≠
∅, for all j
=
1
,
r
-
1
¯. Next, for each program p
i, i
=
1
,
k
¯, we find the complexity class C
j
(
n
)
=
Θ
̿
(
f
j
(
n
)
,
f
j
+
1
(
n
)
) such that g
i
(
n
)
∈
C
j
(
n
). Sometimes, the function g
i
(
n
) can be simultaneous in two consecutive complexity classes C
j
(
n
) and C
j
+
1
(
n
) (according to Proposition 20, C
j
(
n
)
∩
C
j
+
1
(
n
)
=
Θ
(
f
j
+
1
(
n
)
)); in such cases we consider that g
i
(
n
) is only in C
j
(
n
).As a result of the method proposed above, we obtain a classification of the programs from the setSP that offers a solution for the problem P
1. This classification is based on the complexity classes Θ
̿
(
f
1
(
n
)
,
f
2
(
n
)
)
,
Θ
̿
(
f
2
(
n
)
,
f
3
(
n
)
)
,
…
,
Θ
̿
(
f
r
-
1
(
n
)
,
f
r
(
n
)
).


### 3.4. Main Symbols Used in the Paper

This subsection contains a brief description of the main symbols used in the paper. In Notations section, one can observe three types of symbols: sets, asymptotic notations, and functions and numbers.


## 3.1. Definition of Weak Theta

Definition 9.
Letg
1
,
g
2
∈
F. One defines the asymptotic notation Weak Theta, denoted by Θ
̿, as follows:(4)
Θ
̿
g
1
n
,
g
2
n
=
f
∈
F
∣
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
kkklkl
such
that
c
1
·
g
1
n
≤
f
n
≤
c
2
·
g
2
n
,
kkkkll
∀
n
≥
n
0
.Remark 10.
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
) represents the set of all complexity functions that are bounded by the functions c
1
·
g
1
(
n
) and c
2
·
g
2
(
n
) for sufficiently large n.Proposition 11.
Letg
1
,
g
2
∈
F. Then(a)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅ if and only if g
1
(
n
)
∈
O
(
g
2
(
n
)
);
(b)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅ if and only if g
2
(
n
)
∈
Ω
(
g
1
(
n
)
).Proof.
(a) “⇒” Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). Then,(5)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
n
≤
f
n
≤
c
2
·
g
2
n
,
∀
n
≥
n
0
.It follows that(6)
∃
c
′
=
c
2
c
1
∈
R
+
∗
,
∃
n
0
′
=
n
0
∈
N
∗
such
that
g
1
n
≤
c
′
·
g
2
n
,
∀
n
≥
n
0
′
.Consequently,(7)
g
1
(
n
)
∈
O
(
g
2
(
n
)
)
.
“⇐” Consider that g
1
(
n
)
∈
O
(
g
2
(
n
)
); it follows that(8)
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
g
1
n
≤
c
·
g
2
n
,
∀
n
≥
n
0
.
From (8), we obtain(9)
∃
c
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
1
·
g
1
n
≤
g
1
n
≤
c
·
g
2
n
,
∀
n
≥
n
0
.
So, we have(10)
∃
c
1
′
=
1
,
c
2
′
=
c
∈
R
+
∗
,
∃
n
0
′
=
n
0
∈
N
∗
such
that
c
1
′
·
g
1
n
≤
g
1
n
≤
c
2
′
·
g
2
n
,
∀
n
≥
n
0
′
.
Consequently,(11)
g
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.
(b) The result follows from (a) using the relation(12)
g
1
(
n
)
∈
O
g
2
n
iff
g
2
(
n
)
∈
Ω
(
g
1
(
n
)
)
.Remark 12.
In all situations in which a proposition or a theorem has as a hypothesis a relation of the formg
1
(
n
)
∈
O
(
g
2
(
n
)
), one implicitly understands that Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅.


## 3.2. Motivation

(a) The first use of our notation is for describing complexity functions with complex behaviour (i.e., functions difficult to be approximated by a single elementary complexity function). As an example, letf
∈
F with the form(13)
f
(
n
)
=
n
2
,
n
=
3
k
,
n
lg
n
,
n
=
3
k
+
1
,
n
,
n
=
3
k
+
2
.If we use the asymptotic notations from Definition3, we may obtain (14)
f
(
n
)
∈
O
(
n
2
)or(15)
f
(
n
)
∈
Ω
(
n
)which are too general descriptions of the behavior of f
(
n
), while the use of Θ is not appropriate.If we use the new asymptotic notation proposed in Definition9, then we obtain(16)
f
(
n
)
∈
Θ
̿
(
n
,
n
2
)
.(b) Usually, the best case, the worst case, and the average case of the running time of an algorithm are described by functions with different behaviours. Also, for all algorithms, the average case is situated between the best case and the worst case. For example, assume that for an algorithmA the best case is represented by f
1
(
n
)
=
n
2
lg
n
+
n and the worst case is represented by f
2
(
n
)
=
n
3
+
n
2.UsingΘ, we obtain that f
1
(
n
)
∈
Θ
(
n
2
lg
n
) and f
2
(
n
)
∈
Θ
(
n
3
). This is a valid description of the two cases of the algorithm, but we need two complexity classes (Θ
(
n
2
lg
n
) and Θ
(
n
3
)) for this analysis.If we useΘ
̿, only one complexity class is necessary. The running time of the algorithm A is fully described by Θ
̿
(
n
2
lg
n
,
n
3
).


## 3.3. An Application of Weak Theta in Artificial Intelligence

In this subsection, we propose an artificial intelligence based solution for the following problem denoted byP
1. “Let SP
=
{
p
1
,
p
2
,
…
,
p
k
} be a set of software programs and P
2 a given problem. Each program p
i, i
=
1
,
k
¯, solves the problem P
2. We make the following assumptions: (
1
) each program p
i, i
=
1
,
k
¯, terminates for each valid input; (
2
) for all programs p
i, i
=
1
,
k
¯, the inputs have the same form; (
3
) the codes of the programs are not available. One asks to find the fastest program(s) from the set SP.”The problemP
1 can be seen as an unsupervised classification problem that can be solved in terms of “Weak Theta.” In this framework, we propose an algorithm that aims to solve the problem P
1. This algorithm uses for the first two steps a simple and common idea for estimating the running time of a software program: “choose several inputs for the program; for each input measure the corresponding running time and then, using this information, find the function that best estimates the running time of the program.”The algorithm can be described as follows.Step 1.
Consider a set of inputs{
input
1
,
input
2
,
…
,
input
q
} of sizes {
s
1
,
s
2
,
…
,
s
q
} (where s
j is the size of input input
j). We run each program p
i, i
=
1
,
k
¯, for all inputs and we obtain the corresponding running times {
t
1
i
,
t
2
i
,
…
,
t
q
i
}. In the end, for each program p
i, i
=
1
,
k
¯, we will have a set of pairs S
i
=
{
(
s
1
,
t
1
i
)
,
(
s
2
,
t
2
i
)
,
…
,
(
s
q
,
t
q
i
)
}.Step 2.
For each programp
i, i
=
1
,
k
¯, we use the data S
i for obtaining a complexity function g
i that best approximates the running time of the program. For this step we may use estimation techniques.Step 3.
First, we choose a set of complexity functions{
f
1
,
f
2
,
…
,
f
r
} such that f
j
(
n
)
∈
O
(
f
j
+
1
(
n
)
), for all j
=
1
,
r
-
1
¯; from Proposition 11, we have Θ
̿
(
f
j
(
n
)
,
f
j
+
1
(
n
)
)
≠
∅, for all j
=
1
,
r
-
1
¯. Next, for each program p
i, i
=
1
,
k
¯, we find the complexity class C
j
(
n
)
=
Θ
̿
(
f
j
(
n
)
,
f
j
+
1
(
n
)
) such that g
i
(
n
)
∈
C
j
(
n
). Sometimes, the function g
i
(
n
) can be simultaneous in two consecutive complexity classes C
j
(
n
) and C
j
+
1
(
n
) (according to Proposition 20, C
j
(
n
)
∩
C
j
+
1
(
n
)
=
Θ
(
f
j
+
1
(
n
)
)); in such cases we consider that g
i
(
n
) is only in C
j
(
n
).As a result of the method proposed above, we obtain a classification of the programs from the setSP that offers a solution for the problem P
1. This classification is based on the complexity classes Θ
̿
(
f
1
(
n
)
,
f
2
(
n
)
)
,
Θ
̿
(
f
2
(
n
)
,
f
3
(
n
)
)
,
…
,
Θ
̿
(
f
r
-
1
(
n
)
,
f
r
(
n
)
).


## 3.4. Main Symbols Used in the Paper

This subsection contains a brief description of the main symbols used in the paper. In Notations section, one can observe three types of symbols: sets, asymptotic notations, and functions and numbers.


## 4. Relations between Weak Theta and Other Asymptotic Notations

Proposition 13.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(17)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
.Proof.
First, we prove the direct inclusion(18)
Θ
̿
g
1
n
,
g
2
n
⊆
Ω
g
1
n
∩
O
g
2
n
.Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). It follows that(19)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
.
From (19), we have that(20)
∃
c
′
=
c
1
∈
R
+
∗
,
∃
n
0
′
=
n
0
∈
N
∗
such
that
c
′
·
g
1
n
≤
f
n
,
∀
n
≥
n
0
′
,
∃
c
′′
=
c
2
∈
R
+
∗
,
∃
n
0
′
′
=
n
0
∈
N
∗
such
that
f
n
≤
c
′′
·
g
2
n
,
∀
n
≥
n
0
′
′
.
So, we have(21)
f
(
n
)
∈
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
.
Next, we prove the reverse inclusion(22)
Ω
g
1
n
∩
O
g
2
n
⊆
Θ
̿
g
1
n
,
g
2
n
.
Letf
(
n
)
∈
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
). It follows that(23)
∃
c
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
′
·
g
1
n
≤
f
n
,
∀
n
≥
n
0
′
,
∃
c
′′
∈
R
+
∗
,
∃
n
0
′
′
∈
N
∗
such
that
f
n
≤
c
′′
·
g
2
n
,
∀
n
≥
n
0
′
′
.
From (23) we have that(24)
∃
c
1
=
c
′
,
c
2
=
c
′′
∈
R
+
∗
,
∃
n
0
=
max
⁡
⁡
n
0
′
,
n
0
′
′
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
.
Consequently,(25)
f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.Corollary 14.
Letg
∈
F. Then Θ
̿
(
g
(
n
)
,
g
(
n
)
)
=
Θ
(
g
(
n
)
).Proof.
From Proposition13, we have that(26)
Θ
̿
(
g
(
n
)
,
g
(
n
)
)
=
Ω
(
g
(
n
)
)
∩
O
(
g
(
n
)
)
.Next, using the relation(27)
Ω
g
n
∩
O
g
n
=
Θ
g
n
,we obtain the result.Proposition 15.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(a)
Θ
(
g
1
(
n
)
)
=
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
O
(
g
1
(
n
)
);
(b)
Θ
(
g
2
(
n
)
)
=
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Ω
(
g
2
(
n
)
).Proof.
(a) First, we prove thatΘ
(
g
1
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
O
(
g
1
(
n
)
). Let f
(
n
)
∈
Θ
(
g
1
(
n
)
). It follows that(28)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
1
(
n
)
,
∀
n
≥
n
0
.From the hypothesis, we have that g
1
(
n
)
∈
O
(
g
2
(
n
)
). So we have(29)
∃
c
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
g
1
(
n
)
≤
c
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
.From (28) and (29), we obtain(30)
∃
c
1
′′
=
c
1
,
c
2
′′
=
c
2
·
c
′
∈
R
+
∗
,
∃
n
0
′
′
=
max
⁡
⁡
n
0
,
n
0
′
∈
N
∗
such
that
c
1
′′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
′
.Consequently,(31)
f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.Using (27), we have that(32)
Θ
(
g
1
(
n
)
)
⊆
O
(
g
1
(
n
)
)
.From (31) and (32), we obtain the result.
We prove the reverse inclusionΘ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
O
(
g
1
(
n
)
)
⊆
Θ
(
g
1
(
n
)
). Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
O
(
g
1
(
n
)
). It follows that(33)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
,
∃
c
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
f
(
n
)
≤
c
′
·
g
1
(
n
)
,
∀
n
≥
n
0
′
.From (33), we obtain(34)
∃
c
1
′′
=
c
1
,
c
2
′′
=
c
′
∈
R
+
∗
,
∃
n
0
′
′
=
max
⁡
⁡
n
0
,
n
0
′
∈
N
∗
such
that
c
1
′′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
1
(
n
)
,
∀
n
≥
n
0
′
′
.Consequently,(35)
f
(
n
)
∈
Θ
(
g
1
(
n
)
)
.
(b) For the proof, one can follow the same idea used for proving (a) and the definition ofΩ.Corollary 16.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(a)
Θ
(
g
1
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
);
(b)
Θ
(
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
).Proof.
The proof follows easily using Proposition15.Proposition 17.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Θ
(
g
1
(
n
)
)
=
Θ
(
g
2
(
n
)
) if and only if g
1
(
n
)
∈
Θ
(
g
2
(
n
)
).Proof.
“⇒” From the hypothesis, we have(36)
g
1
n
∈
Θ
g
1
n
=
Θ
̿
g
1
n
,
g
2
n
=
Θ
g
2
n
.
“⇐” We consider that g
1
(
n
)
∈
Θ
(
g
2
(
n
)
). It follows that(37)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
1
′
·
g
2
(
n
)
≤
g
1
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
.From Corollary 16 and the relation g
1
(
n
)
∈
Θ
(
g
2
(
n
)
), we have that(38)
Θ
g
1
n
⊆
Θ
̿
g
1
n
,
g
2
n
,
Θ
(
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.We have to prove that(39)
Θ
̿
g
1
n
,
g
2
n
⊆
Θ
g
1
n
,
(40)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
Θ
(
g
2
(
n
)
)
.
Letf
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). It follows that(41)
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′
′
∈
N
∗
such
that
c
1
′′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
′
.Using (37), we have that(42)
∃
c
1
′′′
=
1
c
1
′
∈
R
+
∗
,
∃
n
0
′
′
′
=
n
0
′
∈
N
∗
such
that
g
2
(
n
)
≤
c
1
′′′
·
g
1
(
n
)
,
∀
n
≥
n
0
′
′
′
.From (41) and (42), we obtain that(43)
∃
c
1
=
c
1
′′
,
c
2
=
c
2
′′
·
c
1
′′′
∈
R
+
∗
,
∃
n
0
=
max
⁡
⁡
n
0
′
′
,
n
0
′
′
′
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
1
(
n
)
,
∀
n
≥
n
0
.Consequently,(44)
f
(
n
)
∈
Θ
(
g
1
(
n
)
)
.The other inclusion, from (40), can be proved using the same idea.Proposition 18.
Letg
1
,
g
2
,
g
3
,
g
4
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
) and g
3
(
n
)
∈
O
(
g
4
(
n
)
). Then Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
) if and only if g
1
(
n
)
∈
Θ
(
g
3
(
n
)
) and g
2
(
n
)
∈
Θ
(
g
4
(
n
)
).Proof.
“⇒” From the hypothesis and Corollary 16, we have that(45)
g
1
n
∈
Θ
̿
g
1
n
,
g
2
n
=
Θ
̿
g
3
n
,
g
4
n
,
g
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.From (45) and Proposition 13, we obtain that(46)
g
1
n
∈
Ω
g
3
n
,
g
2
(
n
)
∈
O
(
g
4
(
n
)
)
.From the hypothesis and Corollary 16, we have that(47)
g
3
n
∈
Θ
̿
g
3
n
,
g
4
n
=
Θ
̿
g
1
n
,
g
2
n
,
g
4
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
=
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.From (47) and Proposition 13, we obtain that(48)
g
3
n
∈
Ω
g
1
n
,
g
4
(
n
)
∈
O
(
g
2
(
n
)
)
.Next, from (48), we have(49)
g
1
n
∈
O
g
3
n
,
g
2
(
n
)
∈
Ω
(
g
4
(
n
)
)
.
From (46) and (49), we deduce that(50)
g
1
(
n
)
∈
Θ
(
g
3
(
n
)
)
g
2
(
n
)
∈
Θ
(
g
4
(
n
)
)
.
“⇐” Consider that g
1
(
n
)
∈
Θ
(
g
3
(
n
)
) and g
2
(
n
)
∈
Θ
(
g
4
(
n
)
). It follows that(51)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
01
∈
N
∗
such
that
c
1
′
·
g
3
(
n
)
≤
g
1
(
n
)
≤
c
2
′
·
g
3
(
n
)
,
∀
n
≥
n
01
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
02
∈
N
∗
such
that
c
1
′′
·
g
4
(
n
)
≤
g
2
(
n
)
≤
c
2
′′
·
g
4
(
n
)
,
∀
n
≥
n
02
.Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). It follows that(52)
∃
c
3
′
,
c
4
′
∈
R
+
∗
,
∃
n
03
∈
N
∗
such
that
c
3
′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
4
′
·
g
2
(
n
)
,
∀
n
≥
n
03
.Using (51) and (52), we have(53)
∃
c
3
′
′
=
c
1
′
·
c
3
′
,
c
4
′
′
=
c
4
′
·
c
2
′′
∈
R
+
∗
,
∃
n
04
=
max
⁡
⁡
n
01
,
n
02
,
n
03
∈
N
∗
such
that
c
3
′
′
·
g
3
(
n
)
≤
f
(
n
)
≤
c
4
′
′
·
g
4
(
n
)
,
∀
n
≥
n
04
.Consequently,(54)
f
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.The other inclusion, Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), can be proved using a similar idea.Proposition 19.
Letg
1
,
g
2
∈
F. Then,(55)
g
1
n
∈
Θ
g
2
n
iff
Θ
̿
g
1
n
,
g
2
n
=
Θ
̿
g
2
n
,
g
1
n
≠
∅
.Proof.
“⇒” Consider that g
1
(
n
)
∈
Θ
(
g
2
(
n
)
). We prove that (56)
Θ
̿
g
1
n
,
g
2
n
⊆
Θ
̿
g
2
n
,
g
1
n
.Since g
1
(
n
)
∈
Θ
(
g
2
(
n
)
), it follows that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Consequently, we obtain the relation Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
≠
∅.
Letf
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). It follows that(57)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
.From the relation g
1
(
n
)
∈
Θ
(
g
2
(
n
)
), we have(58)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
1
′
·
g
2
(
n
)
≤
g
1
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
.Next, using the relation(59)
g
1
n
∈
Θ
g
2
n
iff
g
2
n
∈
Θ
g
1
n
,we obtain that(60)
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
1
′′
·
g
1
(
n
)
≤
g
2
(
n
)
≤
c
2
′′
·
g
1
(
n
)
,
∀
n
≥
n
0
′′
.From (57), (58), and (60), we have that(61)
∃
c
¯
1
=
c
1
·
c
1
′
,
c
¯
2
=
c
2
·
c
2
′′
∈
R
+
∗
,
∃
n
¯
0
=
max
⁡
⁡
n
0
,
n
0
′
,
n
0
′′
∈
N
∗
such
that
c
¯
1
·
g
2
(
n
)
≤
f
(
n
)
≤
c
¯
2
·
g
1
(
n
)
,
∀
n
≥
n
¯
0
.Consequently,(62)
f
(
n
)
∈
Θ
̿
(
g
2
(
n
)
,
g
1
(
n
)
)
.The proof of Θ
̿
(
g
2
(
n
)
,
g
1
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
) follows the same idea used for the first inclusion.
“⇐” We consider that Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
2
(
n
)
,
g
1
(
n
)
)
≠
∅.
Letf
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
2
(
n
)
,
g
1
(
n
)
). It follows that(63)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
1
′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
1
′′
·
g
2
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
1
(
n
)
,
∀
n
≥
n
0
′′
.From (63), we obtain(64)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
g
1
(
n
)
≤
c
2
′
c
1
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
1
′′
c
2
′′
·
g
2
(
n
)
≤
g
1
(
n
)
,
∀
n
≥
n
0
′′
.Using (64), we have(65)
∃
c
1
=
c
1
′′
c
2
′′
,
c
2
=
c
2
′
c
1
′
∈
R
+
∗
,
∃
n
0
=
max
⁡
⁡
n
0
′
,
n
0
′′
∈
N
∗
such
that
c
1
·
g
2
(
n
)
≤
g
1
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
.Consequently,(66)
g
1
(
n
)
∈
Θ
(
g
2
(
n
)
)
.


## 5. Membership, Inclusion, Intersection, and Union

Proposition 20.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). Then,(a)
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
);
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
);
(b)
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
)
∩
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
=
Θ
(
f
(
n
)
);
(c)
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
)
∪
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
).Proof.
(a) Leth
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
). It follows that(67)
∃
c
1
,
c
2
∈
R
+
∗
,
∃
n
0
∈
N
∗
such
that
c
1
·
g
1
(
n
)
≤
h
(
n
)
≤
c
2
·
f
(
n
)
,
∀
n
≥
n
0
.From the relation f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), we have(68)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
1
′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
.From (68), we obtain(69)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
2
·
c
1
′
·
g
1
(
n
)
≤
c
2
·
f
(
n
)
≤
c
2
·
c
2
′
·
g
2
(
n
)
,
kkkkkkkkkkkkkkkkkkkkkkkllllllllllllkkkkl
∀
n
≥
n
0
′
.Using (67) and (69), we have that(70)
∃
c
1
′′
=
c
1
,
c
2
′′
=
c
2
·
c
2
′
∈
R
+
∗
,
∃
n
0
′′
=
max
⁡
⁡
n
0
,
n
0
′
∈
N
∗
such
that
c
1
′′
·
g
1
(
n
)
≤
h
(
n
)
≤
c
2
′′
·
g
2
(
n
)
,
∀
n
≥
n
0
′′
.Consequently,(71)
h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.For proving that Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), one can follow the same idea used for the first relation of (a).
(b) From Corollary16, it follows that (72)
Θ
f
n
⊆
Θ
̿
g
1
n
,
f
n
∩
Θ
̿
f
n
,
g
2
n
.Let h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
)
∩
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
). It follows that(73)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
c
1
′
·
g
1
(
n
)
≤
h
(
n
)
≤
c
2
′
·
f
(
n
)
,
∀
n
≥
n
0
′
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
1
′′
·
f
(
n
)
≤
h
(
n
)
≤
c
2
′′
·
g
2
(
n
)
,
∀
n
≥
n
0
′′
.From (73), we obtain(74)
∃
c
1
=
c
1
′′
,
c
2
=
c
2
′
∈
R
+
∗
,
∃
n
0
=
max
⁡
(
n
0
′
,
n
0
′′
)
∈
N
∗
such
that
c
1
·
f
(
n
)
≤
h
(
n
)
≤
c
2
·
f
(
n
)
,
∀
n
≥
n
0
.Consequently,(75)
h
(
n
)
∈
Θ
(
f
(
n
)
)
.
(c) The proof follows from (a).Proposition 21.
Letg
1
,
g
2
,
g
3
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
) and g
2
(
n
)
∈
O
(
g
3
(
n
)
). Then,(a)
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
≠
∅,
(b)
g
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
).Proof.
(a) We use the transitivity of the complexity class “O” (see Proposition 4), described as(76)
if
g
1
n
∈
O
g
2
n
,
g
2
n
∈
O
g
3
n
then
g
1
n
∈
O
g
3
n
.Hence, from the hypothesis and (76), we have(77)
g
1
(
n
)
∈
O
(
g
3
(
n
)
)
.Next, using (77) and Proposition 11(a), we obtain that (78)
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
≠
∅
.
(b) Using the hypothesis and Proposition4(d), we have that(79)
g
2
(
n
)
∈
Ω
(
g
1
(
n
)
)
.Consequently, using (79) and the hypothesis, we have(80)
g
2
(
n
)
∈
Ω
(
g
1
(
n
)
)
∩
O
(
g
3
(
n
)
)
.From (80) and Proposition 13, we have that(81)
g
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
.Proposition 22.
Letg
1
,
g
2
,
g
3
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
) and g
2
(
n
)
∈
O
(
g
3
(
n
)
). Let f
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), f
2
(
n
)
∈
Θ
̿
(
g
2
(
n
)
,
g
3
(
n
)
), and f
∈
F with the form (82)
f
(
n
)
=
f
1
(
n
)
,
i
f
n
∈
M
1
f
2
(
n
)
,
i
f
n
∈
M
2
,where M
1 and M
2 are two infinite subsets of  N
∗ such that M
1
∪
M
2
=
N
∗ and M
1
∩
M
2
=
∅. Then f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
).Proof.
Using the hypothesis and Proposition21, we have that(83)
g
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
.Also, from the hypothesis and Proposition 4(b), we obtain(84)
g
1
(
n
)
∈
O
(
g
3
(
n
)
)
.From (84), (83), and Proposition 20, we have(85)
Θ
̿
g
1
n
,
g
2
n
⊆
Θ
̿
g
1
n
,
g
3
n
,
Θ
̿
(
g
2
(
n
)
,
g
3
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
.Using (85) and the hypothesis, we obtain that(86)
f
1
n
∈
Θ
̿
g
1
n
,
g
3
n
,
f
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
.Consequently,(87)
f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
)
.Proposition 23.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Let f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). Then,(a)
iff
(
n
)
∈
Θ
(
g
1
(
n
)
) or f
(
n
)
∈
Θ
(
g
2
(
n
)
), then (88)
Θ
̿
g
1
n
,
f
n
∪
Θ
̿
f
n
,
g
2
n
=
Θ
̿
g
1
n
,
g
2
n
;
(b)
ifΘ
̿
(
g
1
(
n
)
,
f
(
n
)
)
∪
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), then (89)
f
(
n
)
∉
ω
g
1
n
o
r
f
(
n
)
∉
o
(
g
2
(
n
)
)
.Proof.
(a) Consider the following.
Case 1. Consider f
(
n
)
∈
Θ
(
g
1
(
n
)
). From Proposition 17, we have that(90)
Θ
̿
g
1
n
,
f
n
=
Θ
f
n
.From (90) and Corollary 16, we have that(91)
Θ
̿
g
1
n
,
f
n
⊆
Θ
̿
f
n
,
g
2
n
.Next, from the relation f
(
n
)
∈
Θ
(
g
1
(
n
)
) and Proposition 18, we have that(92)
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
=
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.
Case 2. Consider f
(
n
)
∈
Θ
(
g
2
(
n
)
). The proof follows the same idea used for proving Case 1.
(b) Suppose for a contradiction thatf
(
n
)
∈
ω
(
g
1
(
n
)
) and f
(
n
)
∈
o
(
g
2
(
n
)
).
Leth
∈
F such that(93)
h
(
n
)
=
g
1
(
n
)
,
if
n
∈
M
1
g
2
(
n
)
,
if
n
∈
M
2
,where M
1 and M
2 are infinite subsets of N
∗ such that M
1
∪
M
2
=
N
∗ and M
1
∩
M
2
=
∅. From the relations g
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
) and g
2
(
n
)
∈
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
) and from Proposition 22 we have that(94)
h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.Since(95)
Θ
̿
g
1
n
,
g
2
n
=
Θ
̿
g
1
n
,
f
n
∪
Θ
̿
f
n
,
g
2
n
,then(96)
h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
)or(97)
h
(
n
)
∈
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
)
.
Case 1. Consider h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
).
From (93) and the relation h
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
f
(
n
)
), we have that(98)
∃
c
1
∈
R
+
∗
,
∃
n
01
∈
N
∗
such
that
g
2
n
≤
c
1
·
f
n
,
∀
n
∈
M
2
,
n
≥
n
01
.Using the relation f
(
n
)
∈
o
(
g
2
(
n
)
), it follows that(99)
∀
c
′
∈
R
+
∗
,
∃
n
0
′
∈
N
∗
such
that
f
(
n
)
<
c
′
·
g
2
(
n
)
,
∀
n
≥
n
0
′
.We take in (99) c
′
=
1
/
c
1 and we obtain that(100)
∃
n
02
∈
N
∗
such
that
f
(
n
)
<
1
c
1
·
g
2
(
n
)
,
∀
n
≥
n
02
.From (98), (100), and the fact that M
2 is an infinite subset of N
∗, we obtain that(101)
∃
n
0
=
max
⁡
⁡
n
01
,
n
02
,
∃
n
∈
M
2
,
n
≥
n
0
such
that
g
2
(
n
)
≤
c
1
·
f
(
n
)
<
g
2
(
n
)which is a contradiction.
Case 2. Consider h
(
n
)
∈
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
).
From (93) and the relation h
(
n
)
∈
Θ
̿
(
f
(
n
)
,
g
2
(
n
)
), we have that(102)
∃
c
1
′
∈
R
+
∗
,
∃
n
01
′
∈
N
∗
such
that
c
1
′
·
f
(
n
)
≤
g
1
(
n
)
,
∀
n
∈
M
1
,
n
≥
n
01
′
.Using the relation f
(
n
)
∈
ω
(
g
1
(
n
)
), it follows that(103)
∀
c
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
′′
·
g
1
(
n
)
<
f
(
n
)
,
∀
n
≥
n
0
′′
.We take in (103) c
′′
=
1
/
c
1
′ and we obtain that(104)
∃
n
02
′
∈
N
∗
such
that
1
c
1
′
·
g
1
(
n
)
<
f
(
n
)
,
∀
n
≥
n
02
′
.From (102), (104), and the fact that M
1 is an infinite subset of N
∗, we obtain that(105)
∃
n
0
′
=
max
⁡
⁡
n
01
′
,
n
02
′
,
∃
n
∈
M
1
,
n
≥
n
0
′
such
that
g
1
(
n
)
<
c
1
′
·
f
(
n
)
≤
g
1
(
n
)which is a contradiction.Proposition 24.
Letg
1
,
g
2
,
g
3
,
g
4
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
) and g
3
(
n
)
∈
O
(
g
4
(
n
)
). Then,(a)
ifg
2
(
n
)
∈
Θ
(
g
3
(
n
)
), then(106)
Θ
̿
g
1
n
,
g
2
n
∩
Θ
̿
g
3
n
,
g
4
n
=
Θ
g
2
n
=
Θ
g
3
n
;
(b)
ifg
2
(
n
)
∈
o
(
g
3
(
n
)
), then(107)
Θ
̿
g
1
n
,
g
2
n
∩
Θ
̿
g
3
n
,
g
4
n
=
∅
;
(c)
ifg
2
(
n
)
∈
ω
(
g
3
(
n
)
), g
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
), and g
3
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), then(108)
Θ
̿
g
1
n
,
g
2
n
∩
Θ
̿
g
3
n
,
g
4
n
=
Θ
̿
g
3
n
,
g
2
n
,where  g
3
n
∉
Θ
g
2
n.Proof.
(a) The relation(109)
Θ
(
g
2
(
n
)
)
=
Θ
(
g
3
(
n
)
)is obvious from g
2
(
n
)
∈
Θ
(
g
3
(
n
)
). We prove that (110)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
=
Θ
(
g
2
(
n
)
)
.
(i) From the hypothesis, one can easily obtain thatΘ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
≠
∅.
Letf
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
). It follows that(111)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
01
∈
N
∗
such
that
c
1
′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
01
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
02
∈
N
∗
such
that
c
1
′′
·
g
3
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
4
(
n
)
,
∀
n
≥
n
02
.From the relation g
2
(
n
)
∈
Θ
(
g
3
(
n
)
), we have that(112)
∃
c
1
′′′
,
c
2
′′′
∈
R
+
∗
,
∃
n
03
∈
N
∗
such
that
c
1
′′′
·
g
3
(
n
)
≤
g
2
(
n
)
≤
c
2
′′′
·
g
3
(
n
)
,
∀
n
≥
n
03
.From (112), we have that(113)
∃
c
3
=
1
c
2
′′′
∈
R
+
∗
,
∃
n
04
=
n
03
∈
N
∗
such
that
c
3
·
g
2
(
n
)
≤
g
3
(
n
)
,
∀
n
≥
n
04
.Using (111) and (113), we obtain(114)
∃
c
4
=
c
1
′′
·
c
3
,
c
5
=
c
2
′
∈
R
+
∗
,
∃
n
05
=
max
⁡
(
n
01
,
n
02
,
n
04
)
∈
N
∗
such
that
c
4
·
g
2
(
n
)
≤
f
(
n
)
≤
c
5
·
g
2
(
n
)
,
∀
n
≥
n
05
.Consequently,(115)
f
(
n
)
∈
Θ
(
g
2
(
n
)
)
.
(ii) From Corollary16, we have(116)
Θ
(
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.From (109) and Corollary 16, we have(117)
Θ
(
g
2
(
n
)
)
=
Θ
(
g
3
(
n
)
)
⊆
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.Using (116) and (117), we obtain that(118)
Θ
(
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.
(b) Suppose for a contradiction that there existsf
∈
F such that f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
). It follows that(119)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
01
∈
N
∗
such
that
c
1
′
·
g
1
(
n
)
≤
f
(
n
)
≤
c
2
′
·
g
2
(
n
)
,
∀
n
≥
n
01
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
02
∈
N
∗
such
that
c
1
′′
·
g
3
(
n
)
≤
f
(
n
)
≤
c
2
′′
·
g
4
(
n
)
,
∀
n
≥
n
02
.From the relation g
2
(
n
)
∈
o
(
g
3
(
n
)
), we have that(120)
∀
c
1
′′′
∈
R
+
∗
,
∃
n
0
′′′
∈
N
∗
such
that
g
2
(
n
)
<
c
1
′′′
·
g
3
(
n
)
,
∀
n
≥
n
0
′′′
.We take in (120) c
1
′′′
=
c
1
′′
/
c
2
′ and we obtain that(121)
∃
n
03
∈
N
∗
such
that
c
2
′
·
g
2
(
n
)
<
c
1
′′
·
g
3
(
n
)
,
∀
n
≥
n
03
.From (119) and (121), we have that(122)
∃
n
0
=
max
⁡
⁡
n
01
,
n
02
,
n
03
∈
N
∗
such
that
c
1
′
·
g
1
n
≤
f
n
≤
c
2
′
·
g
2
n
<
c
1
′′
·
g
3
(
n
)
kkkkkkkkkkkkkkkl
≤
f
(
n
)
≤
c
2
′′
·
g
4
(
n
)
,
∀
n
≥
n
0which is a contradiction.
We conclude that(123)
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
=
∅
.
(c) From relationg
2
(
n
)
∈
ω
(
g
3
(
n
)
), we have that(124)
g
2
(
n
)
∈
Ω
(
g
3
(
n
)
)
.Thus, from Proposition 11, it follows that(125)
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
)
≠
∅
.Furthermore, we prove that g
3
(
n
)
∉
Θ
(
g
2
(
n
)
). Suppose for a contradiction that g
3
(
n
)
∈
Θ
(
g
2
(
n
)
). It follows that(126)
∃
c
¯
1
,
c
¯
2
∈
R
+
∗
,
∃
n
¯
0
∈
N
∗
such
that
c
¯
1
·
g
2
(
n
)
≤
g
3
(
n
)
≤
c
¯
2
·
g
2
(
n
)
,
∀
n
≥
n
¯
0
.Thus, from (126), we have that(127)
∃
c
̿
1
=
1
c
¯
1
∈
R
+
∗
,
∃
n
̿
0
=
n
¯
0
∈
N
∗
such
that
g
2
(
n
)
≤
c
̿
1
·
g
3
(
n
)
,
∀
n
≥
n
̿
0
.From g
2
(
n
)
∈
ω
(
g
3
(
n
)
), we have that(128)
∀
c
¯
′
∈
R
+
∗
,
∃
n
¯
0
′
∈
N
∗
such
that
c
¯
′
·
g
3
(
n
)
<
g
2
(
n
)
,
∀
n
≥
n
¯
0
′
.
We take in (128) c
¯
′
=
c
̿
1 and we obtain that(129)
∃
n
̿
0
′
∈
N
∗
such
that
c
̿
1
·
g
3
(
n
)
<
g
2
(
n
)
,
∀
n
≥
n
̿
0
′
.From (127) and (129), we obtain that(130)
∃
n
0
=
max
⁡
⁡
n
̿
0
,
n
̿
0
′
∈
N
∗
such
that
g
2
(
n
)
≤
c
̿
1
·
g
3
(
n
)
<
g
2
(
n
)
,
∀
n
≥
n
0which is a contradiction. Consequently, we have g
3
(
n
)
∉
Θ
(
g
2
(
n
)
).
Now, we prove thatΘ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
=
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
).
(i) First, we prove thatΘ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
⊆
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
).
From the hypothesis one can easily obtain thatΘ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
≠
∅.
Letf
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
). It follows that(131)
∃
c
1
′
,
c
2
′
∈
R
+
∗
,
∃
n
′
0
∈
N
∗
such
that
c
1
′
·
g
1
n
≤
f
1
n
≤
c
2
′
·
g
2
n
,
∀
n
≥
n
0
′
,
∃
c
1
′′
,
c
2
′′
∈
R
+
∗
,
∃
n
0
′′
∈
N
∗
such
that
c
1
′′
·
g
3
(
n
)
≤
f
1
(
n
)
≤
c
2
′′
·
g
4
(
n
)
,
∀
n
≥
n
0
′′
.From (131), we obtain that(132)
∃
c
1
=
c
1
′′
,
c
2
=
c
2
′
∈
R
+
∗
,
∃
n
0
=
max
⁡
⁡
n
0
′
,
n
0
′′
∈
N
∗
such
that
c
1
·
g
3
(
n
)
≤
f
1
(
n
)
≤
c
2
·
g
2
(
n
)
,
∀
n
≥
n
0
.Consequently,(133)
f
1
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
)
.
(ii) We prove thatΘ
̿
(
g
3
(
n
)
,
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
).
Letf
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
). From Proposition 13, we have(134)
f
2
n
∈
Ω
g
3
n
,
(135)
f
2
(
n
)
∈
O
(
g
2
(
n
)
)
.From the hypothesis and Proposition 13, we have(136)
g
2
n
∈
Ω
g
3
n
∩
O
g
4
n
,
(137)
g
3
(
n
)
∈
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
.From (134), (137), and Proposition 4 (transitivity of Ω), we have that(138)
f
2
(
n
)
∈
Ω
(
g
1
(
n
)
)
.From (135), (136), and Proposition 4 (transitivity of O), we have that(139)
f
2
(
n
)
∈
O
(
g
4
(
n
)
)
.Using (135), (138), and Proposition 13, we have(140)
f
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.Using (134), (139), and Proposition 13, we have(141)
f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.Consequently,(142)
f
2
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∩
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
)
.Proposition 25.
Letg
1
,
g
2
,
…
,
g
k
∈
F such that g
i
(
n
)
∈
O
(
g
i
+
1
(
n
)
), ∀
i
=
1,2
,
…
,
k
-
1. Then(a)
Θ
̿
(
g
i
(
n
)
,
g
i
+
1
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
k
(
n
)
), ∀
i
=
1,2
,
…
,
k
-
1;
(b)
Θ
̿
(
g
i
(
n
)
,
g
i
+
1
(
n
)
)
∩
Θ
̿
(
g
i
+
1
(
n
)
,
g
i
+
2
(
n
)
)
=
Θ
(
g
i
+
1
(
n
)
), ∀
i
=
1,2
,
…
,
k
-
2;
(c)
⋃
i
=
1
k
-
1
Θ
̿
(
g
i
(
n
)
,
g
i
+
1
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
k
(
n
)
).Proof.
(a) Leti
∈
{
1,2
,
…
,
k
-
1
} arbitrarily fixed.
From the hypothesis and Proposition4 (transitivity of O), we have(143)
g
1
n
∈
O
g
i
n
,
(144)
g
i
+
1
(
n
)
∈
O
(
g
k
(
n
)
)
.Let f
(
n
)
∈
Θ
̿
(
g
i
(
n
)
,
g
i
+
1
(
n
)
). Then, using Proposition 13, we have(145)
f
n
∈
Ω
g
i
n
,
(146)
f
(
n
)
∈
O
(
g
i
+
1
(
n
)
)
.From (143) and Proposition 4 (transpose symmetry), we have(147)
g
i
(
n
)
∈
Ω
(
g
1
(
n
)
)
.Thus, from (145), (147), and Proposition 4 (transitivity of Ω), we obtain(148)
f
(
n
)
∈
Ω
(
g
1
(
n
)
)
.From (146), (144), and Proposition 4 (transitivity of O), we obtain(149)
f
(
n
)
∈
O
(
g
k
(
n
)
)
.Using (148), (149), and Proposition 13, we have that(150)
f
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
k
(
n
)
)
.
(b) Leti
∈
{
1,2
,
…
,
k
-
2
} arbitrarily fixed. Since(151)
g
i
n
∈
O
g
i
+
1
n
g
i
+
1
n
∈
Ω
g
i
n
,
g
i
+
1
n
∈
O
g
i
+
2
n
,we obtain, using Proposition 13, the relation(152)
g
i
+
1
n
∈
Θ
̿
g
i
n
,
g
i
+
2
n
.Next, using Proposition 20(b), we obtain that(153)
Θ
̿
(
g
i
(
n
)
,
g
i
+
1
(
n
)
)
∩
Θ
̿
(
g
i
+
1
(
n
)
,
g
i
+
2
(
n
)
)
=
Θ
(
g
i
+
1
(
n
)
)
.
(c) The proof results easily from (a).


## 6. Some Relations between Complexity Functions

Proposition 26.
Letg
1
,
g
2
,
g
3
,
g
4
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
) and g
3
(
n
)
∈
O
(
g
4
(
n
)
). Let f
1
,
f
2
∈
F such that f
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
) and f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
). Then,(a)
ifg
2
(
n
)
∈
O
(
g
3
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
);
(b)
ifg
2
(
n
)
∈
Θ
(
g
3
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
);
(c)
ifg
2
(
n
)
∈
o
(
g
3
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
);
(d)
ifg
2
(
n
)
∈
o
Θ
(
g
3
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
).Proof.
(a) From the hypothesis and Proposition13, we have that(154)
f
1
n
∈
Ω
g
1
n
∩
O
g
2
n
,
f
2
(
n
)
∈
Ω
(
g
3
(
n
)
)
∩
O
(
g
4
(
n
)
)
.It follows that(155)
f
1
n
∈
O
g
2
n
,
g
3
(
n
)
∈
O
(
f
2
(
n
)
)
.Next, using the relation g
2
(
n
)
∈
O
(
g
3
(
n
)
) and Proposition 4 (the transitivity of O), we obtain the relation(156)
f
1
(
n
)
∈
O
(
f
2
(
n
)
)
.In the end, using Definition 5, we obtain that(157)
f
1
(
n
)
∈
C
(
f
2
(
n
)
)
.
((b), (c), and (d)) The proof follows from (a) using the relations(158)
Θ
g
3
n
⊆
O
g
3
n
,
o
g
3
n
⊆
O
g
3
n
,
o
Θ
(
g
3
(
n
)
)
⊆
O
(
g
3
(
n
)
)
.Proposition 27.
Letg
1
,
g
2
,
g
3
,
g
4
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
), g
2
(
n
)
∈
ω
(
g
3
(
n
)
), g
3
(
n
)
∈
O
(
g
4
(
n
)
), g
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
), and g
3
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
). Let f
1
,
f
2
∈
F such that f
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
) and f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
). Then,(a)
iff
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
) and f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
);
(b)
iff
1
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
) and f
2
(
n
)
∈
Θ
̿
(
g
2
(
n
)
,
g
4
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
);
(c)
iff
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
) and f
2
(
n
)
∈
Θ
̿
(
g
2
(
n
)
,
g
4
(
n
)
), then f
1
(
n
)
∈
C
(
f
2
(
n
)
).Proof.
(a) Sinceg
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
) then, from Proposition 13, we have that(159)
g
2
(
n
)
∈
Ω
(
g
3
(
n
)
)
.Next, from Proposition 11, we have that(160)
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
)
≠
∅
.From f
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
3
(
n
)
), f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
2
(
n
)
), and Proposition 13, we obtain that(161)
f
1
n
∈
O
g
3
n
,
g
3
(
n
)
∈
O
(
f
2
(
n
)
)
.Thus, from Proposition 4 (the transitivity of O), we have(162)
f
1
(
n
)
∈
O
(
f
2
(
n
)
)
.Consequently,(163)
f
1
(
n
)
∈
C
(
f
2
(
n
)
)
.
((b) and (c)) The proof follows the same idea used for (a).Remark 28.
In Proposition27, the hypothesis g
2
(
n
)
∈
ω
(
g
3
(
n
)
) is not used in the proof. The purpose of this hypothesis is to emphasize that Propositions 26 and 27 discuss disjoint cases.Proposition 29.
There existg
1
,
g
2
,
g
3
,
g
4
,
f
1
,
f
2
∈
F with the following properties: (i1) g
1
(
n
)
∈
O
(
g
2
(
n
)
), (i2) g
2
(
n
)
∈
ω
(
g
3
(
n
)
), (i3) g
3
(
n
)
∈
O
(
g
4
(
n
)
), (i4) g
3
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), (i5) g
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
), (i6) f
1
(
n
)
∈
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
), and (i7) f
2
(
n
)
∈
Θ
̿
(
g
3
(
n
)
,
g
4
(
n
)
) such that f
1
(
n
)
∉
C
(
f
2
(
n
)
).Proof.
Letg
1
(
n
)
=
n, g
2
(
n
)
=
n
7, g
3
(
n
)
=
n
2, and g
4
(
n
)
=
n
9.
The properties (i1)–(i5) are easily verified sincen
∈
O
(
n
7
), n
7
∈
ω
(
n
2
), n
2
∈
O
(
n
9
), n
2
∈
Θ
̿
(
n
,
n
7
), and n
7
∈
Θ
̿
(
n
2
,
n
9
).
Let(164)
f
1
n
=
n
5
,
f
2
(
n
)
=
n
4
,
if
n
∈
M
1
n
6
,
if
n
∈
M
2
,where M
1 and M
2 are two infinite subsets of N
∗ such that M
1
∪
M
2
=
N
∗ and M
1
∩
M
2
=
∅. One can easily verify that(165)
f
1
n
∈
Θ
̿
n
,
n
7
,
f
2
(
n
)
∈
Θ
̿
(
n
2
,
n
9
)
.For proving that f
1
(
n
)
∉
C
(
f
2
(
n
)
), we start from the following relation (see Proposition 8):(166)
C
(
f
2
(
n
)
)
=
O
(
f
2
(
n
)
)
∪
Ω
(
f
2
(
n
)
)
.Suppose for a contradiction that(167)
f
1
(
n
)
∈
O
(
f
2
(
n
)
)
.It follows that(168)
∃
c
1
∈
R
+
∗
,
∃
n
01
∈
N
∗
such
that
f
1
(
n
)
≤
c
1
·
f
2
(
n
)
,
∀
n
≥
n
01
.Using (168) for n
∈
{
m
∈
M
1
∣
m
≥
n
01
}, we obtain(169)
n
5
≤
c
1
·
n
4which is false for n
>
c
1. We know that there exists n
>
c
1, n
∈
M
1, because M
1 is an infinite subset of N
∗. Consequently,(170)
f
1
(
n
)
∉
O
(
f
2
(
n
)
)
.Using the same idea one can prove that(171)
f
1
(
n
)
∉
Ω
(
f
2
(
n
)
)
.From (170) and (171), it follows that(172)
f
1
(
n
)
∉
C
(
f
2
(
n
)
)
.


## 7. The Set of Complexity Functions Comparable with Two Given Complexity Functions

Definition 30.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). We define the set of complexity functions comparable with g
1
(
n
) and g
2
(
n
), denoted by C
̿
(
g
1
(
n
)
,
g
2
(
n
)
), as follows: (173)
C
̿
g
1
n
,
g
2
n
=
o
g
1
n
∪
o
Θ
g
1
n
∪
Θ
̿
g
1
n
,
g
2
n
∪
Θ
ω
g
2
n
∪
ω
(
g
2
(
n
)
)
.Proposition 31.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then, (174)
C
̿
g
1
n
,
g
2
n
=
O
g
1
n
∪
Ω
g
1
n
∩
O
g
2
n
∪
Ω
(
g
2
(
n
)
)
.Proof.
From Definition30, we have(175)
C
̿
g
1
n
,
g
2
n
=
o
g
1
n
∪
o
Θ
g
1
n
∪
Θ
̿
g
1
n
,
g
2
n
∪
Θ
ω
(
g
2
(
n
)
)
∪
ω
(
g
2
(
n
)
)
.From Corollary 16, we have that(176)
Θ
g
1
n
⊆
Θ
̿
g
1
n
,
g
2
n
,
Θ
(
g
2
(
n
)
)
⊆
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.It follows that(177)
Θ
̿
g
1
n
,
g
2
n
=
Θ
g
1
n
∪
Θ
̿
g
1
n
,
g
2
n
∪
Θ
(
g
2
(
n
)
)
.Consequently, we obtain(178)
C
̿
g
1
n
,
g
2
n
=
o
g
1
n
∪
o
Θ
g
1
n
∪
Θ
g
1
n
∪
Θ
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
∪
Θ
(
g
2
(
n
)
)
∪
Θ
ω
(
g
2
(
n
)
)
∪
ω
(
g
2
(
n
)
)
.Next, using Propositions 7 and 13, we have that(179)
C
̿
g
1
n
,
g
2
n
=
O
g
1
n
∪
Ω
g
1
n
∩
O
g
2
n
∪
Ω
(
g
2
(
n
)
)
.Proposition 32.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(a)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
C
(
g
1
(
n
)
);
(b)
ifg
1
(
n
)
∈
Θ
(
g
2
(
n
)
), then C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
C
(
g
1
(
n
)
).Proof.
(a) From Proposition31 it follows that(180)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
O
(
g
1
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
∪
Ω
(
g
2
(
n
)
)
.Since g
1
(
n
)
∈
O
(
g
2
(
n
)
), we have that(181)
Ω
(
g
2
(
n
)
)
⊆
Ω
(
g
1
(
n
)
)
.From (180), (181), and Proposition 8, we obtain that(182)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
O
(
g
1
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
=
C
(
g
1
(
n
)
)
.
(b) Sinceg
1
(
n
)
∈
Θ
(
g
2
(
n
)
), one can easily prove that(183)
O
g
1
n
=
O
g
2
n
,
Ω
(
g
1
(
n
)
)
=
Ω
(
g
2
(
n
)
)
.Using (183) and Proposition 31, we have(184)
C
̿
g
1
n
,
g
2
n
=
O
g
1
n
∪
Ω
g
1
n
∩
O
g
1
n
∪
Ω
(
g
1
(
n
)
)
.Next, from Proposition 4(e) we obtain that(185)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
O
(
g
1
(
n
)
)
∪
Θ
(
g
1
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
.Consequently,(186)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
O
(
g
1
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
.Thus, from Proposition 8, it follows that(187)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
C
(
g
1
(
n
)
)
.Proposition 33.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(a)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
C
(
g
2
(
n
)
);
(b)
ifg
1
(
n
)
∈
Θ
(
g
2
(
n
)
) then C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
C
(
g
2
(
n
)
).Proof.
The proof follows the same idea used for proving Proposition32.Proposition 34.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then,(a)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
⊆
C
(
g
1
(
n
)
)
∪
C
(
g
2
(
n
)
);
(b)
ifg
1
(
n
)
∈
Θ
(
g
2
(
n
)
) then C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
C
(
g
1
(
n
)
)
∪
C
(
g
2
(
n
)
).Proof.
The proof follows easily using Propositions32 and 33.Proposition 35.
Letg
1
,
g
2
∈
F such that g
1
(
n
)
∈
O
(
g
2
(
n
)
). Then, (188)
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
=
C
(
g
1
(
n
)
)
∩
C
(
g
2
(
n
)
)
.Proof.
Using Proposition8, we have that(189)
C
g
1
n
∩
C
g
2
n
=
O
g
1
n
∪
Ω
g
1
n
∩
O
(
g
2
(
n
)
)
∪
Ω
(
g
2
(
n
)
)
.From (189), using the distributivity of intersection over union, we obtain(190)
C
g
1
n
∩
C
g
2
n
=
O
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
∪
Ω
(
g
2
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
∪
Ω
(
g
2
(
n
)
)
=
O
g
1
n
∩
O
g
2
n
∪
O
g
1
n
∩
Ω
g
2
n
∪
Ω
(
g
1
(
n
)
)
∩
O
(
g
2
(
n
)
)
∪
Ω
(
g
1
(
n
)
)
∩
Ω
(
g
2
(
n
)
)
.Next, using the relations g
1
(
n
)
∈
O
(
g
2
(
n
)
) and O
(
g
1
(
n
)
)
∩
Ω
(
g
2
(
n
)
)
⊆
O
(
g
1
(
n
)
), we obtain that(191)
C
g
1
n
∩
C
g
2
n
=
O
g
1
n
∪
Ω
g
1
n
∩
O
g
2
n
∪
Ω
(
g
2
(
n
)
)
.Consequently, using Proposition 31, we have(192)
C
(
g
1
(
n
)
)
∩
C
(
g
2
(
n
)
)
=
C
̿
(
g
1
(
n
)
,
g
2
(
n
)
)
.


## 8. Conclusions

In this paper, we defined a new asymptotic notation based on two given complexity functions and then we proposed and proved several properties of this new notation, classified in the following four categories:(i)
relations between “Weak Theta” and other asymptotic notations;
(ii)
properties concerning membership, inclusion, intersection, and union;
(iii)
some relations between complexity functions;
(iv)
properties related to “Weak Theta” and the set of complexity functions comparable with two given complexity functions.The main benefit of this new asymptotic notation is the possibility to characterize a complexity function by catching it between two given complexity functions, thus allowing approximation of functions with complex behaviours that are hard to be analyzed using other existent asymptotic notations.



---

*Source: 912962-2015-10-04.xml*