1st Assignment Solution

$35.00 $30.80


Problem 1 (25pts)


Do Problem 2.3-3 on page 39 in CLRS. Justify your answers.


Problem 2 (25pts)


  1. Rank the following functions by order of growth; that is, find an ar-rangement f1, f2, ··· , f24of the functions satisfying f1 = O(f2), f2 = O(f3), ··· , f23 = O(f24). Briefly show your work for this problem.
lg(lg n) nlg lg n nlog6 5 n2 n! 22n
( 4 )n n2 + n ( 3 )n lg(n!) 22n n1/ lg n
3 4
    2n     nn    
lnlnn n2n lnn n lg n
2lg n (lg n)lg n n       1 lg(lg n)
  lg n











  1. Partition your list into equivalence classes such that f (n) and g(n) are in the same class if and only if f (n) = Θ(g(n)).


Problem 3 (50pts)


Do Problem 4-3 (a) to (e) on page 108 in CLRS. Justify your answers.