ii. Bob believes he invented a faster algorithm than Karatsuba's algorithm. Each n-digit number is partitioned...

Transcribed Image Text:

ii. Bob believes he invented a faster algorithm than Karatsuba's algorithm. Each n-digit number is partitioned into three (n/3)-digit numbers. For example, 199054321 is di- vided into three 3-digit numbers 199, 054, 321. Then Bob recursively performs some multiplications of (n/3)-digit numbers, in a way similar to Karatsuba's algorithm. In- stead of making three (n/2)-digit multiplications, he believes he needs six (n/3)-digit multiplications. Write down a recurrence formula expressing the time complexity of his algorithm. Solve the recurrence. Is his algorithm faster or slower than Karatsuba's? [7 marks] (You may find the following table of common log values useful.) 3 4 6 7 8 9 5 1.58 2 2.32 2.58 2.81 3 3.17 1.26 1.46 1.63 1.77 1.89 2 1 n log₂ n log, n ii. Bob believes he invented a faster algorithm than Karatsuba's algorithm. Each n-digit number is partitioned into three (n/3)-digit numbers. For example, 199054321 is di- vided into three 3-digit numbers 199, 054, 321. Then Bob recursively performs some multiplications of (n/3)-digit numbers, in a way similar to Karatsuba's algorithm. In- stead of making three (n/2)-digit multiplications, he believes he needs six (n/3)-digit multiplications. Write down a recurrence formula expressing the time complexity of his algorithm. Solve the recurrence. Is his algorithm faster or slower than Karatsuba's? [7 marks] (You may find the following table of common log values useful.) 3 4 6 7 8 9 5 1.58 2 2.32 2.58 2.81 3 3.17 1.26 1.46 1.63 1.77 1.89 2 1 n log₂ n log, n

Answer rating: 100% (QA)

Lets denote the time complexity of Bobs algorithm as Tn where n is the number of digits in each numb... View the full answer