Cryptography Reference
In-Depth Information
B
./
>
./
>
Figure 6.1
Negligible, nonnegligible (noticeable), and other functions.
or “steps” that must be executed. Often a step is taken to mean a bit operation. For
some algorithms, however, it is more convenient to have a step mean something
more comprehensive, such as a comparison, a machine instruction, a machine clock
cycle, a modular multiplication, or anything else along these lines.
In either case, the running time of an algorithm can be measured in the worst
or average case:
•
The
worst-case running time
of an algorithm is an upper bound on the running
time for any input, expressed as a function of the input size.
•
The
average-case running time
of an algorithm is the average running time
over all inputs of a fixed size, also expressed as a function of the input size.
In modern cryptography, it is common to call a computation efficient if it
terminates within a worst-case running time that is polynomial in the input size.
Polynomial functions and polynomial-time algorithms as formally introduced in
Definitions 6.3 and 6.4 are defined along these lines.
Definition 6.3 (Polynomial function)
A function
f
(
n
)
is called
polynomial
if
f
(
n
)=
O
(
n
c
)
for some
c
∈
N
. Otherwise, it is called
super-polynomial
.
In some literature, a polynomial function is called
polynomially bounded
,
and a super-polynomial function is called
nonpolynomially bounded
. In this topic,
however, we don't use these terms, and we say that a function is either polynomial
or super-polynomial.
If
and
c
are constants with 0
<<
1
<c
, then the following functions are
listed in increasing order of their asymptotic growth rates:
1
<
ln ln
n<
ln
n<e
√
ln
n
ln ln
n
<n
<n
c
<n
ln
n
<c
n
<n
n
<c
c
n
