We are interested in measuring the time complexity of executing a sequence of n invocations of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
We are interested in measuring the time complexity of executing a sequence of n invocations of the following function with the array A initially containing all 0's. Function increment (A) Input: A[0..m-1] is an array of 0-1 bits representing a binary counter Output: A after its value incremented by 1 modulo 2m i 0 while i < m and A[i] = 1 do A[i] +0 i + i +1 end if i < m then | A[i] + 1 end (a) Note the time complexity of the function is proportional to number of itera- tions of the while loop and can be 0(m) in the worst case. Thus concluding that the sequence of n invocations takes O(mn) time is incorrect as it is a loose bound. We can use amortized complexity analysis to improve the bound. Using accounting method show that the amortized complexity of a single invocation in a sequence of n invocations is 0(1). [Hint: Assume cost of a function is measured by number of bit flips(0 to 1 and 1 to 0) required. Argue that the amortized cost is 2 units per invocation] (b) What potential function will you use for the amortized analysis ? Derive the amortized time complexity using this potential function. We are interested in measuring the time complexity of executing a sequence of n invocations of the following function with the array A initially containing all 0's. Function increment (A) Input: A[0..m-1] is an array of 0-1 bits representing a binary counter Output: A after its value incremented by 1 modulo 2m i 0 while i < m and A[i] = 1 do A[i] +0 i + i +1 end if i < m then | A[i] + 1 end (a) Note the time complexity of the function is proportional to number of itera- tions of the while loop and can be 0(m) in the worst case. Thus concluding that the sequence of n invocations takes O(mn) time is incorrect as it is a loose bound. We can use amortized complexity analysis to improve the bound. Using accounting method show that the amortized complexity of a single invocation in a sequence of n invocations is 0(1). [Hint: Assume cost of a function is measured by number of bit flips(0 to 1 and 1 to 0) required. Argue that the amortized cost is 2 units per invocation] (b) What potential function will you use for the amortized analysis ? Derive the amortized time complexity using this potential function.
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
The volume V(T) (in cm3) follows V(T) = l + T2. Suppose we are interested in measuring the properties of a substance at temperature of absolute zero (which is 0 degrees Kelvin). However, we cannot...
-
The hardness H(T) follows H(T) = 10.0/1 + T. Suppose we are interested in measuring the properties of a substance at temperature of absolute zero (which is 0 degrees Kelvin). However, we cannot...
-
A machine requires three hours to make a unit of Product A and nine hours to make a unit of Product B. Last month the machine operated for 957 hours, producing a total of 145 units. How many units of...
-
In 2016, common stockholders received $6 per share in annual dividends. The market price per share for common stock was $24. Compute the dividend yield for common stock?
-
A graduating student keeps applying for jobs until she has three offers. The probability of getting an offer at any trial is 0.48. a. What is the expected number of applications? What is the...
-
Describe the privileging and credentialing process.
-
Statement of Cash Flows Suppose a company lengthens the time it takes to pay suppliers. How would this affect the statement of cash flows? How sustainable is the change in cash flows from this...
-
What annual interest rate would you need to earn if you wanted a $4,575 per month contribution starting 1 month from today to grow to $1,644,350 in 17 years (Assume monthly compounding and that you...
-
The following table summarizes the operating results for Bene Petits first year of operations: Bene Petit First year operating data: Single (1 serving) Dual (2 servings) Family (4 servings) Total...
-
As you have read in this first chapter and the assigned primary sources and media this week, several worlds collided, each having a long history of their own that would affect the way they saw the...
-
Describe the functions of chimney in a boiler.
-
What are the most favorable sites for installing wind turbines?
-
What is the origin of biomass energy? What are the main advantages and disadvantages of it?
-
Write short notes on solar energy, wind power energy, biomass, and geothermal energy.
-
What do you mean by renewable and nonrenewable sources of energy?
-
Hyman J. The importance of assessing confounding and effect modication in research involving periodontal disease and systemic diseases. J Clin Periodontol 2006; 33: 102103 1. How are these two...
-
Differentiate the following terms/concepts: a. Personality types and money attitudes b. Planners and avoiders c. Moderating and adapting to biases d. "Perfectible judges" and "incorrigible judges"
-
It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiple-array representation. (This is the case in a...
-
Suppose we have stored n keys in a hash table of size m, with collisions resolved by chaining, and that we know the length of each chain, including the length L of the longest chain. Describe a...
-
VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axes), so that we represent a...
-
A child on a sled slides down an icy slope, starting at a speed of \(2.5 \mathrm{~m} / \mathrm{s}\). The slope makes a \(15^{\circ}\) angle with the horizontal. After sliding \(10 \mathrm{~m}\) down...
-
You hold a puck at the top of an ice-covered ramp inclined at \(60^{\circ}\) with respect to the vertical. Your friend stands nearby on level ground and holds a ball at the same height \(h\) above...
-
You throw a ball straight up with an initial speed of \(10 \mathrm{~m} / \mathrm{s}\). (a) What is the ball's instantaneous acceleration at instant \(t_{1}\), just after it leaves your hand; at...
Study smarter with the SolutionInn App