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 gn are in the same class if and only if f (n) = theta(g(n). n square root n 2^n 23/n n^2 nlog^2 n 132 n log logn n^2 log n n^3 2^n/2 n log n n^1.5 n log (n2) 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) = 0(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.