1. (Analysis of Algorithms) Find an asymptotically-tight bound for the following

Question

1. (Analysis of Algorithms) Find an asymptotically-tight bound for the following algorithm. Show your work. Algorithm 1 The Karatsuba multiplication algorithm Preconditions: p(x)-2nd: pix' and q(x)- maximum degreen-l Postconditions: KARATSUBA returns p(x) q(x) qix' are polynomials with n 1 terms and i-0 l: procedure KARATSUBA (int n,Numeric() p,Numeric() q) if n 1 then D p(x) and q(x) are constants else Split p(x) and q(x) into two halves 5: 6: 8 Compute two intermediate sums Sp(X) pn(x) + pL(X) Sq(X) qn(x) + q1(x) 10: Recursively multiply TH(X) KARATSUBAG, ph(x), qn(x)) rL(X) KARATSUBAG. PL (X), q1(x) rs(X) KARATSUBAG Sp (X), so(x) 12: 13 r(x) XnTH(X) + X2 (g(x)-TH(X)-n(x)) + rL(X) Combine the results 14 15: end if 16: return r(x) 17: end procedure

Explanation / Answer

There are 3 recursive calls to the function with half of the input size.

The other algo can be solved in O(1) time.

So our recurrence relation will be

T(n) = 3 T(n/2) + O(1).

Applying the master theorem to the above recurrence relation

Case 1 . Applies, so the tight bound will be nlog 2 3.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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