Problem 3. Rank the following functions by order of growth; that is, find an arr

Question

Problem 3. Rank the following functions by order of growth; that is, find an arrangement g1, g2, ... of the functions satisfying g1 = O(g2), g2 = O(g3),? Partition your list into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n) = theta(g(n). n root n 2^n 23/n n^2 n log^2n 132 nlog logn n^2logn n3 2n/2 nlogn n^1.5 nlog(n^2) Problem 4. Suppose T1(n) = O(f (n)) and T2(n) = O(f (n)). Which of the following are true? 1. T1(n) + T2(n) = O(f (n)) 2. T1(n) - T2(n) = O(f(n)) 3. T1(n)/T2(n) = O(1) 4. T1(n) = O(T2(n))

Explanation / Answer

1) 2n > sqrt(2)n > n3 > n2logn > n2 > nlog2n> n1.5 > nlogn2 >nlogn > n > nloglogn > sqrt(n) > 132 > 23/n

4)

1) True

2) False

3) False

4)False

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.