Cryptography Reference
In-Depth Information
6.3
ASYMPTOTIC ORDER NOTATION
In complexity theory, one is often interested in the asymptotic behavior of the com-
plexity of a computation as a function of the input size
5
or some other parameter(s).
This is where asymptotic analysis and asymptotic order notation come into play.
In what follows, we only consider functions that are defined for positive integers
and take on real values that are positive for some
n
+
and
≥
n
0
.Let
f
:
N
→
R
+
be such functions. The following asymptotic bounds are frequently
used in complexity theory.
g
:
N
→
R
Asymptotic upper bound:
If there exist a positive constant
c
and a positive integer
n
0
such that 0
≤
f
(
n
)
≤
cg
(
n
) for all
n
≥
n
0
, then we write
f
(
n
)=
O
(
g
(
n
))
.
If
g
(
n
) is constant (and independent from
n
), then we write
f
(
n
)=
O
(1),or
f
=
O
(1) in short. Note that this applies even if the constant is very large,
such as 2
128
.Furthermore,if0
≤
f
(
n
)
<cg
(
n
) for all
n
≥
n
0
, then we write
f
(
n
)=
o
(
g
(
n
))
.
Asymptotic lower bound:
If there exist a positive constant
c
and a positive integer
n
0
such that 0
≤
cg
(
n
)
≤
f
(
n
) for all
n
≥
n
0
, then we write
f
(
n
)=Ω(
g
(
n
))
.
Asymptotic tight bound:
If there exist positive constants
c
1
and
c
2
, and a positive
integer
n
0
such that
c
1
g
(
n
)
≤
f
(
n
)
≤
c
2
g
(
n
) for all
n
≥
n
0
, then we write
f
(
n
)=Θ(
g
(
n
))
.
5
The input size is the size or length of the (binary) word that is needed to represent the input (for a
well-defined representation method).
