Cryptography Reference
In-Depth Information
O
(log(
n
)
a
)
O
(log(
n
)
b
)
Exercise
2.1.4
Show
that
if
f
(
n
)
=
and
g
(
n
)
=
then
(
f
+
O
(log(
n
)
max
{
a,b
}
) and (
fg
)(
n
)
O
(log(
n
)
a
+
b
). Show
g
)(
n
)
=
f
(
n
)
+
g
(
n
)
=
=
f
(
n
)
g
(
n
)
=
that
O
(
n
c
)
O
(2
c
log(
n
)
).
=
We also present the “little
o
”, “soft
O
”, “big Omega” and “big Theta” notation. These
will only ever be used in this topic for functions of a single argument.
Definition 2.1.5
Let
f,g
:
N → R
>
0
. Write
f
(
n
)
=
o
(
g
(
n
)) if
lim
n
→∞
f
(
n
)
/g
(
n
)
=
0
.
O
(
g
(
n
)) if there is some
m
O
(
g
(
n
)log(
g
(
n
))
m
). Write
Write
f
(
n
)
=
∈ N
such that
f
(
n
)
=
f
(
n
)
=
(
g
(
n
)) if
g
(
n
)
=
O
(
f
(
n
)). Write
f
(
n
)
=
(
g
(
n
)) if
f
(
n
)
=
O
(
g
(
n
)) and
g
(
n
)
=
O
(
f
(
n
)).
O
(
g
(
n
)) then there is some
m
Exercise 2.1.6
Show that if
g
(
n
)
=
O
(
n
) and
f
(
n
)
=
∈ N
O
(
n
log(
n
)
m
).
such that
f
(
n
)
=
Definition 2.1.7
(Worst-case asymptotic complexity.) Let
A
be a deterministic algorithm
and let
t
(
n
) be a bound on the running time of
A
on every problem of input size
n
bits.
A
is
polynomial-time
if there is an integer
k
O
(
n
k
).
∈ N
such that
t
(
n
)
=
A
is
superpolynomial-time
if
t
(
n
)
(
n
c
) for all
c
∈ R
>
1
.
A
is
exponential-time
if there is a constant
c
2
>
1 such that
t
(
n
)
=
O
(
c
2
).
=
A
is
subexponential-time
if
t
(
n
)
O
(
c
n
) for all
c
=
∈ R
>
1
.
Exercise 2.1.8
Show that
n
a
log(log(
n
))
and
n
a
log(
n
)
,forsome
a
∈ R
>
0
, are functions that are
(
n
c
) and
O
(
c
n
) for all
c
∈ R
>
1
.
For more information about computational complexity, including the definitions of
complexity classes such as P and NP, see Chapters 2 to 4 of [
539
], Chapter 13 of [
265
],
Chapter 15 of [
154
], Chapter 7 of [
509
] or Chapter 34 of [
136
]. Definition
2.1.7
is for
uniform
complexity, as a single algorithm
A
solves all problem instances. One can also
consider
non-uniform complexity
, where one has an algorithm
A
and, for each
n
∈ N
,
polynomially sized auxiliary input
h
(
n
) (the hint) such that if
x
is an
n
-bit instance of the
computational problem then
A
(
x,h
(
n
)) solves the instance. An alternative definition is a
sequence
A
n
of algorithms, one for each input size
n
, and such that the description
of the algorithm is polynomially bounded. We stress that the hint is not required to be
efficiently computable. We refer to Section 4.6 of Talbot and Welsh [
539
] for details.
Complexity theory is an excellent tool for comparing algorithms, but one should always
be aware that the results can be misleading. For example, it can happen that there are several
algorithms to solve a computational problem and that the one with the best complexity is
slower than the others for the specific problem instance one is interested in (e.g., see
Remark
2.2.5
).
∈ N
