Suppose you have correctly determined some c and n, to prove g(n) E ?(f(n)) whic

Question

Suppose you have correctly determined some c and n, to prove g(n) E ?(f(n)) which of the following is not necessarily true? A. c may be decreased B. c may be increased C. no may be increased D. f(n)E Olg(n Suppose you are using the substitution method to establish a 3 4. bound on a recurrence T(n) and you already know that 7(n) (log n) and T( nje ? nj Which of the following cannot be shown as an improvement? D. T(n) E O(1) 5. The function n + log n is in which set? B. ?(log n) C. ?(n) D. O( n log n /n 6. Which of the following is not true? B. nlogn E O D log ne ?(loglog n) /n C. g(n)eo(f(n))-f(n)EO(g(n))

Explanation / Answer

3. C. n0 may be increased.

Explanation: n0 is chosen such that n >= n0. If n0 is increased, then it is not necessary that n >= n0.

4. D. T(n) belongs to O(1)

Explanation: O(1) is lesser than logn and n3. Hence, we cannot show it as an improvement.

5. c) Theta(n)

Explanation: n + log n can be expressed in terms of Theta(n) since log n < n.

6. C

Explanation:

The reverse is not true.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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