Algorithm A for solving problem P has a time complexity TA(n) for an instance of

Question

Algorithm A for solving problem P has a time complexity TA(n) for an instance of size n. We do not know the asymptotic order of T base A(n). However, we know that T base A(n) =7 T(n/2) + f base A(n), where f base A(n) = (n^2). Algorithm B for solving problem P has a timecomplexity TB(n) for an instance of size n. We do not know the asymptotic order of TB(n).However, we know that T base B(n) = 47 T(n/4) + f base B(n), where f base B(n) = (n^2).Compute the asymptotic orders for T base A(n) and T base B(n) using the master method. You need tospecify a, b, logb a, and decide the case. You also need to write the derived conclusion.Which algorithm is asymptotically faster?

Explanation / Answer

T base A(n) =7 · T(n/2) + f base A(n) f base A(n) = T(n^2) T base B(n) = 47 T(n/4) + f base B(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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