1st_-Assignment:Solution

Description

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 f₁, f₂, ··· , f₂₄ of the functions satisfying f₁ = O(f₂), f₂ = O(f₃), ··· , f₂₃ = O(f₂₄). 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

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

2