*Due Thursday, Nov. 14.*

- For each of the above 5 relations prove
*transitivity*

(e.g.*f=*for any positive functions**O**(g)**AND**g=**O**(h) => f=**O**(h),*f, g, h*)

*Extra Credit:*

Which of these 5 relations are*reflexive*?

relation*Definition:*is**X**()if and only if for any function*reflexive**f . f=***X**(f)

Prove the answers (both positive and negative)

- Which of these relations are
*symmetric*and which are*anti-symmetric*?

relation*Definition:*is**X**()if and only if for any functions*symmetric**f,g . f=*relation**X**(g) <=> g=**X**(f).

is**X**()if and only if for any functions*anti-symmetric**f,g . f=***X**(g) => NOT g=**X**(f).

Prove the answers

- Order the following functions
*f(n)*in terms of their o(), O() and Q() relations as well as you can (i.e. selecting the most precise of them):

*n, 100n+2*sqrt^{500}, 2^{n}, n^{2}, n^{1/3}, 5n^{1/2}+3n^{1/3},*(**n), n*^{2}+n^{3}, lg n, lg(n^{5}), (lg n)^{5}, n2^{n}, n^{n}