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