Answer each subquestion, explaining/justifying your answer (a) Will a given algo

Question

Answer each subquestion, explaining/justifying your answer

(a) Will a given algorithm A with running time in theta (n) always provide better performance than a given algorithm B in theta(n^2)? (b) Algorithm C consists of a sequence of calls to four functions with running times in theta (n^2), theta (log n), theta (n^3), and theta (n^2). (There are no branches/loops/etc. in C; it consists only of the four function calls, and constant time operations). Algorithm D is in theta (n^3). Which algorithm is preferable in general (in terms of performance), or is there not enough information to tell?

Explanation / Answer

a)
   No, for larger value of n, A will have always better
   performance than B.
   But for smaller value of n, B can have better performance thatn A.

b)
  
   C call four functions with performance: O(n^2), O(logn), O(n^3), O(n^2)

   So, generally we ignore lower order terms to get overall performance:

       here: O(n^3) > O(n^2) > O(logn)

       So, overall performance of C: O(n^3)

   Now, D has O(n^3) performance.

   So, both has same overall performance.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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