subject
Mathematics, 06.05.2020 00:18 neptunesx

The conventional way of multiplying two n-bit integers requires O(n2) time. There are much better ways of multiplying long integers, based on a divide-and-conquer approach. For example, we can break each n-bit integer into n/2-bit halves, and produce the result by making 3 recursive calls to n/2-bit multiplications (which are themselves done in this clever way) and several additions of n/2-bit integers. Since addition of n-bit numbers only requires O(n) time, you get a recurrence for the running time of T(n) = 3T(n/2) + cn for some constant c (which, asymptotically, doesn't matter). This algorithm is sometimes referred to as the "Karatsuba-Ofman (KO) Algorithm." Hypothetically, we can beat the KO approach if we can break our two n-bit numbers into y pieces of length n/y, and perform the multiplication of n-bit numbers by using x recursive multiplications of n/y bit numbers plus any constant number of additions of n/y-bit numbers. What is the relationship between x and y that would make this hypothetical algorithm have a lower running time than the KO Algorithm? Identify one such pair below. Note, because the exact calculation requires the computation of logarithms, you may wish to find and use a scientific calculator of some sort.

ansver
Answers: 2

Another question on Mathematics

question
Mathematics, 21.06.2019 14:40
Which statement most accurately describe why the division property of exponents does not apply to the expression (-8)^2/(-3)^4
Answers: 2
question
Mathematics, 21.06.2019 16:00
This race was first held in 1953 on august 16th. every decade the race finishes with a festival. how many years is this?
Answers: 2
question
Mathematics, 21.06.2019 19:10
Which of the following is the shape of a cross section of the figure shown below
Answers: 3
question
Mathematics, 21.06.2019 20:30
What is 1/3x5 on anuber line what does it look like on a number line
Answers: 3
You know the right answer?
The conventional way of multiplying two n-bit integers requires O(n2) time. There are much better wa...
Questions