Mathematics for Computer Science

Chapter 14 Sums and Asymptotics436

or
nŠD.1Co.1//

p

2n

n

e

n

:

In such cases, the true meaning is

HnDln.n/C Cf.n/

for somef.n/wheref.n/DO.1=n/, and

nŠD.1Cg.n//

p

2n

n

e

n

whereg.n/Do.1/. These transgressions are OK as long as you (and your reader)
know what you mean.

14.7.5 Omega

Suppose you want to make a statement of the form “the running time of the algo-
rithm is a least... ”. Can you say it is “at leastO.n^2 /”? No! This statement is
meaningless since big-oh can only be used forupperbounds. For lower bounds,
we use a different symbol, called “big-Omega.”

Definition 14.7.14.Given functionsf;gWR!R, define

f D.g/

to mean
gDO.f /:
For example,x^2 D.x/, 2 xD.x^2 /, andx=100D.100xC

p
x/.
So if the running time of your algorithm on inputs of sizenisT.n/, and you
want to say it is at least quadratic, say

T.n/D.n^2 /:
Likewise, there is also a symbol called little-omega, analogous to little-oh, to
denote that one function grows strictly faster than another function.

Definition 14.7.15.For functionsf;gWR!Rwithfnonnegative, define

f D!.g/

to mean
gDo.f /:
For example,x1:5D!.x/and

p
xD!.ln^2 .x//.
The little-omega symbol is not as widely used as the other asymptotic symbols
we defined.