problem.md

Problems 1 : Asymptotic behavior of polynomials

---

Answer

显而易见.

Problems 2 : Relative asymptotic growths

---

Indicate for each pair of expressions (A,B) in the table below, whether A is O, o, Ω, ω, or Θ of B. Assume that k≥1, ϵ>0, and c>1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.

Answer

A	B	O	o	Ω	ω	Θ
		yes	yes	no	no	no
		yes	yes	no	no	no
		no	no	no	no	no
		no	no	yes	yes	no
		yes	no	yes	no	yes
		yes	no	yes	no	yes

For this problem, some people point out that

for 0 < epsilon < 1,

lg^k n > n^epsilon

and for epsilon >= 1,

lg^k n) < n^epsilon

Therefore, the correct answer is YES YES YES YES YES

issue 103

Problems 3 : Ordering by asymptotic growth rates

---

a. Rank the following functions by order of growth; that is, find an arrangement of the functions satisfying . Partition your list into equivalence classes such that functions and are in the same class if and only if .

b. Give an example of a single nonnegative function such that for all functions in part (a), is neither nor .

Answer

a.

b.

---

Follow @louis1992 on github to help finish this task.