Information Technology Reference
In-Depth Information
A linear function is a polynomial of degree 1. An exponential function is a function of the
form E ( x )= a x for some real a - for example, 2 1 . 5 = 2 . 8284271 ... .The logarithm to the
base a of b , denoted log a b , is the value of x such that a x = b . For example, the logarithm to
base 2 of 2 . 8284271 ... is 1.5 and the logarithm to base 10 of 100 is 2. A function f ( x ) is
polylogarithmic if for some polynomial p ( x ) we can write f ( x ) as p (log 2 x ) ; that is, it is a
polynomial in the logarithm of x .
Two other functions used often in this topic are the floor and ceiling functions. Their
domains are the reals, but their codomains are the integers. The ceiling function , denoted
, maps the real x to the smallest integer greater or equal to it. The floor
function , denoted
x
: ￿
x
: ￿
, maps the real x to the largest integer less than or equal to
3 . 5
= 4and
15 . 0001
= 16. Similarly,
3 . 5
= 3and
15 . 0001
= 15. The
it. Thus,
following bounds apply to the floor and ceiling functions.
f ( x )
f ( x )
f ( x )
1
f ( x )
f ( x )
f ( x )+ 1
As an example of the application of the ceiling function we note that
log 2 n
is the number
of bits necessary to represent the integer n .
1.2.8 Rate of Growth of Functions
Throughout this topic we derive mathematical expressions for quantities such as space, time,
and circuit size. Generally these expressions describe functions f : ￿
from the non-
negative integers to the reals, such as the functions f 1 ( n ) and f 2 ( n ) defined as
f 1 ( n )= 4 . 5 n 2 + 3 n
f 2 ( n )= 3 n + 4 . 5 n 2
When n is large we often wish to simplify expressions such as these to make explicit their
dominant or most rapidly growing term. For example, for large values of n the dominant terms
in f 1 ( n ) and f 2 ( n ) are 4 . 5 n 2 and 3 n respectively, as we show. A term dominates when n is
large if the value of the function is approximately the value of this term, that is, if the function
is within some multiplicative factor of the term.
To highlight dominant terms we introduce the big Oh , big Omega and big Theta no-
tation. They are defined for functions whose domains and codomains are the integers or the
reals.
DEFINITION 1.2.1 Let f : ￿
and g : ￿
be two functions whose domains and
codomains are either the integers or the reals. If there are positive constants x 0 and K> 0 such
that for all
|
x
|≥
x 0 ,
|
f ( x )
|≤
K
|
g ( x )
|
we write
f ( x )= O ( g ( x ))
and say that “ f ( x ) is big Oh of g ( x ) ”oritgrowsnomorerapidlyin x than g ( x ) .Underthe
same conditions we also write
g ( x )=Ω( f ( x ))
Search WWH ::




Custom Search