Q  Notation:
For a given function g (n) :
Q (g(n)) = { f (n) : $ constants c_{1}, c_{2},
n_{0} ³ 0 £ c_{1 }g (n) £
f (n) £ c_{2 }g (n) " n ³ n_{0}
This means: At some point F (n) is sandwiched between c_{1 }g (n) and c_{2 }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 nonnegative. This means that g (n) must be as well.
Example Problem:
Show that f (n) = n^{2}/2  3n Î Q ( n^{2} )  we must find n_{0}, c_{1},c_{2 }for this definition that fit the equation:
c_{1 }n^{2} £ n^{2}/2  3n £ c_{2 }n^{2} " n
³ n_{0}
c_{1 } £ 1/2  3/n £ c_{2 }by dividing by n^{2}
If n ³ 1 then 1/2  3/n £ 1/2 by making c_{2} equal to 1/2
1/2  3/n ³ 1/14 when n ³ 7 ( 1/2  3/n = 0 when n = 6 )
So c_{1 }= 1/14, c_{2 } = 1/2, n_{0 }= 7
Note: other constants work, but we FOUND a set that does.
Consider the contradiction 6 n^{3 } ¹ Q ( n^{2} ) Suppose this were true:
6 n^{3 }£ c_{2 }n^{2} " n ³ n_{0}
6 ^{ }£ c_{2}/n " n ³ n_{0} then n £ c_{2}/6
A note on condensing expressions: f (n) = an^{2} + bn + c is Q ( n^{2} ), in fact:
P (n ) = 

a_{d}n^{d} + ....+ a_{0}  degree d polynomial is Q ( n^{d} ) 
(proofs are in the text book)
