The following algorithm computes the product of two non-negative integers x and y 1. Precondition:...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
The following algorithm computes the product of two non-negative integers x and y 1. \\ Precondition: x >=y >=0 2. int Mult (int x, int y) { 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.) int R=0; int a-x, b=y; while (b>0){ } if (b% 2 == 1) R+= a; a<<=1; b>>=1; return R; a) Give the exact number of bit shifts executed (lines 8 and 9) as a function of y. Justify. b) Give the time complexity of this algorithm using the big-Oh notation. Give the simplest possible expression inside your big-Oh. The following algorithm computes the product of two non-negative integers x and y 1. \\ Precondition: x >=y >=0 2. int Mult (int x, int y) { 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.) int R=0; int a-x, b=y; while (b>0){ } if (b% 2 == 1) R+= a; a<<=1; b>>=1; return R; a) Give the exact number of bit shifts executed (lines 8 and 9) as a function of y. Justify. b) Give the time complexity of this algorithm using the big-Oh notation. Give the simplest possible expression inside your big-Oh.
Expert Answer:
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date:
Students also viewed these accounting questions
-
(i) 8 9 10 11 12 (ii) 7 9 10 11 13 (iii) 7 8 10 12 13 (a) Without doing any computations, order the data sets according to increasing value of standard deviations. (b) Why do you expect the...
-
Accounting March February 6 7 8 9 Master Schedule for Day-Glo Solar Panels January 1 2. 3 4 5 120 95 100 120 135 140 102 125 115 120 165Solar panel product structure tree 1 Solar Panel Week...
-
Find integers x and y such that 2x 3y = 6 4 .
-
1. The standard price per unit of materials is used in the calculation of which of the following variances? Materials price variance Materials quantity variance a NO NO b NO YES c YES NO d YES YES 2...
-
British Airways, Plc. (BA), a U.K. company, prepares its financial statements according to International Financial Reporting Standards. BA's annual report for the year ended March 31, 2009, which...
-
Selected accounts of Downtown Galleries show the following: For each account, identify the item or items that should appear on a statement of cash flows prepared by the direct method. State where to...
-
Trinity Companys Fabrication Department incurred \($105,000\) of factory overhead cost in producing gears and sprockets. The two products consumed a total of 15,000 direct machine hours. Of that...
-
Oakdale, Inc., is a subsidiary of Solomon Publishing and specializes in the publication and distribution of reference books. Oakdales sales for the past year exceeded $18 million, and the company...
-
Sweeten Company had no jobs in progress at the beginning of the year and no beginning inventories. It started, completed, and sold only two jobs during the yearJob P and Job Q. The company uses a...
-
A corporation that manufactures field rifles for the Department of Defense operates a production line that turns out finished firing pins. To monitor the process, an inspector randomly selects five...
-
Propose the arrow-pushing mechanism for the product of the dehydration reaction. OH H,SO, heal
-
I. In each of the following independent situations, determine the dividends received deduction. Assume that none of the corporate shareholders own 20% or more of the stock in the corporations paying...
-
Welch Corporation just paid its annual dividend of $2.00 per share. The firm is expected to grow at a rate of 15 percent for the next three years and then at 6 percent per year thereafter. The...
-
Mary was so excited about the holiday shopping season that she could hardly wait for the Black Friday sales. She got up early and spent all day at her favorite store, Mega Deals, shopping. Mary was...
-
The following diagram represents the ownership of issued share capital of the companies in a group. What is the total non-controlling interest in D Ltd? A: 20 per cent B: 33.6 per cent C: 60 per...
-
A U.S. investor is considering investing $100 million in Fiat stock in Italy. The stock has an expected return of 5% in euros, including the dividend yield, and the investor is forecasting a 3%...
-
What can you infer about each company\'s overall business strategy and the organization s performance? How are these differences in strategic type likely played out in how each company manages human...
-
Ball bearings are widely used in industrial applications. You work for an industrial food machinery manufacturer and your role is to design the driveshaft assembly on a new type of equipment that...
-
Show that we can prove that P(n, k) is true for all pairs of positive integers n and k if we show a) P(1, 1) is true and P(n, k) [P(n + 1, k) P(n, k + 1)] is true for all positive integers n and k....
-
In Exercise find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices. d e
-
Describe the extended Euclidean algorithm using pseudocode. The extended Euclidean algorithm can be used to express gcd(a, b) as a linear combination with integer coefficients of the integers a and...
-
After an intense period of negotiation, Global Enterprises Corporation TA 2, 3 agreed to purchase all of the outstanding common shares of The Carlton Corporation. The agreed-upon price was \($294\)...
-
Aussie Steaks Inc. operates a chain of steak restaurants in the United States. On January 1, 2015, the company had \($500\) million in assets. On January 1, 2015, the company acquired 25 percent of...
-
On January 1, 2015, Tradiciones, Inc., established Tradiciones de Mexico, a wholly-owned, self-sustaining Mexican subsidiary with assets valued at 48 million pesos. The peso (P) is the functional...
Study smarter with the SolutionInn App