## Q - Notation:

For a given function g (n) :
Q (g(n)) = { f (n) : \$ constants c1, c2, n0  ³  0  £  c1 g (n)   £  f (n) £  c2 g (n)  " n   ³  n0

This means: At some point F (n) is sandwiched between c1 g (n) and c2 g (n) :

from Cormen figure 2.1

Q ( g (n) ) is a set of functions, yet we write " f (n) = Q ( g (n) )" to mean that f (n) Î Q ( g (n) ) We use set notation because of sandwiching for  n   ³    f (n) is equal to g (n) to within a constant factor, therefore g (n) is an asymptotically tight bound for f (n).

Note: The definition requires all f (n) Î Q ( g (n) ) to be asymptotically non-negative. This means that g (n) must be as well.

Example Problem:

Show that f (n) = n2/2 - 3n  Î  Q ( n2 )  -- we must find n0, c1,c2 for  this definition that fit the equation:

c1 n2   £  n2/2 - 3n  £  c2 n2    " n   ³  n0

c1   £  1/2 - 3/n  £  cby dividing by  n2

If n ³  1 then 1/2 - 3/n £  1/2  by making c2 equal to 1/2

1/2 - 3/n  ³  1/14 when n  ³ 7   ( 1/2 - 3/n = 0 when n = 6 )

So c1 = 1/14, c2   = 1/2,  n=  7

Note: other constants work, but we FOUND a set that does.

Consider the contradiction  6 n ¹  Q ( n2 ) Suppose this were true:

6 n£  c2 n2   " n   ³  n0

6   £  c2/n  " n   ³  n0 then n  £  c2/6

A note on condensing expressions:  f (n) = an2  + bn + c is Q ( n2 ), in fact:

P (n )    =
 d å i = 0 aini     =
adnd + ....+ a0  -- degree d polynomial is  Q ( nd )

(proofs are in the text book)

 Growth of Functions - 2 of 5