Let x and y be two n-digit binary numbers, where n is a power of 3....

Transcribed Image Text:

Let x and y be two n-digit binary numbers, where n is a power of 3. Let L, XM and R consist of the first third, middle third, and final third of the digits of x, so that 2n x = 2³ xL +2³xM + R, and define yL, YM, and yr analogously. 1. Express ry in terms of XL, XM, XR, YL, YM, YR. Simplify your answer. 2. Give a recursive algorithm that calculates the above polynomial with a recurrence relation of T(n) = 6T(n/3) + O(n). Let x and y be two n-digit binary numbers, where n is a power of 3. Let L, XM and R consist of the first third, middle third, and final third of the digits of x, so that 2n x = 2³ xL +2³xM + R, and define yL, YM, and yr analogously. 1. Express ry in terms of XL, XM, XR, YL, YM, YR. Simplify your answer. 2. Give a recursive algorithm that calculates the above polynomial with a recurrence relation of T(n) = 6T(n/3) + O(n).