CS-113. Problem Set 5

Due Thursday, Nov. 14.


O, o, Q, W, w asymptotic relations

  1. 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)

  1. 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)

  1. 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

  1. 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,     n1/3,     5n1/2+3n1/3,   sqrt(
    n),     n2+n3,    lg n,    lg(n5),     (lg n)5,     n2n,    nn