CS-113. Problem Set 5
Due Thursday, Nov. 14.
O, o, Q, W, w
- For each of the above 5 relations prove transitivity
(e.g. f=O(g) AND g=O(h) => f=O(h),
for any positive functions f, g, h)
- Extra Credit:
Which of these 5 relations are reflexive?
Definition: relation X() is reflexive
if and only if for any function f . f=X(f)
Prove the answers (both positive and negative)
- Which of these relations are symmetric
and which are anti-symmetric?
Definition: relation X() is symmetric
if and only if for any functions f,g . f=X(g) <=> g=X(f).
relation X() is anti-symmetric if and only if
for any functions 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+2500, 2n,
n2+n3, lg n, lg(n5),
(lg n)5, n2n,