are the important terms of a complexity expression. It estimates the asymptotic order of the
complexity of an algorithm and helps to compare algorithms between each other. Recall that if f
and g are two function from and to integers, then we say that f = O(g) if f(n)≤C.g(n) when
n>N, for some constants C and N.
We write f = Θ(g) when the functions f and g are of the same order, which means that
both equalities f = O(g) and g = O(f) hold.
Comparing functions through their asymptotic orders leads to these kind of inequalities :
O(n
0.7
) < O(n) < O(n.log(n)), or O(n
log(n)
) < O(log(n)
n
) < O(n!).
Within sequential models of machine one can distinguish further types of computations :
off-line, on-line and real-time. These types are related also to efficiency. It is understood that
real-time computations are more efficient than general on-line, and that on-line computations
are more efficient than off-line. Each algorithm is an off-line algorithm : "off-line" conceptually
means that the whole input data can be put into the memory before the actual computation
starts. We are not interested then in the intermediate results computed by the algorithm, but
only the final result is sought (though this final result can be a sequence or a vector). The time
complexity is measured by the total time from the moment the computation starts (with all
input data previously memorized) up to the final termination. In contrast, an on-line algorithm
is like a sequential transducer. The portions of the input data are "swallowed" by the algorithm
step after step, and after each step an intermediate result is expected (related to the input data
read so far). It then reads the next portion of the input, and so on. In on-line algorithms the
input can be treated as an infinite stream of data, and so we are not mainly interested in the
termination of the algorithm for all such data. The main interest for us is the total time T(n) for
which we have to wait to get the n-th first outputs. The time T(n) is measured starting at the
beginning of the whole computation (activation of the transducer). Suppose that the input data
is a sequence and that after reading the n-th symbol we want to print "1" if the text read to this
moment contains a given pattern as a suffix, otherwise we print "0". Hence we have two
streams of data : the stream of input symbols and an output stream of answers "1" or "0". The
main feature of the on-line algorithm is that we have to give an output value before reading the
next input symbol.
The real time computations are these on-line algorithms which are in a certain sense optimal;
the elapsing time between reading two consecutive input symbols (the time spent for
computing only the last output value) should be bounded by a constant. Most linear on-line
algorithms are in fact real-time.
We are mostly interested in off-line computations whose worst case time is linear,
however also on-line and real-time computations as well as average complexities will be
sometimes shortly discussed in the book.