Suppose an algorithm was found for multiplying two n-digit numbers which recursi

Question

Suppose an algorithm was found for multiplying two n-digit numbers which recursively multiplied four pairs of n/3-digit numbers then combined the results in O(n) time.

• Provide the recurrence relation for this new algorithm

• Use the master method to determine to find the solution to the recurrence relation in Big-Oh notation.

• Would this be faster than multiplying two n-digit numbers using a divide and conquer teachnique which recursively multiplied three pairs of n/2-digit numbers then combined the results in O(n) time

Explanation / Answer

As per my understanding, recurrence relation of given algo. will be

T(n) = 4T(n/3) + O(n)

From master theorem, since, a>bk . Therefore,

T(n) = O(nlogba) = O(nlog34) = O(n1.26)

For another algo, recurrence relation is given as:

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

which gives a = 3, b = 2, k=1

Since, a>bk . Therefore,

T(n) = O(nlogba) = O(nlog23) = O(n1.58)

Since, n1.26 < n1.58. Therefore, algo. 1 is faster than algo. 2.

Hope it helps, feels free to comment in case of any query.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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