Help please!! I need help with this problem. no coding just math In January, you
ID: 3766400 • Letter: H
Question
Help please!! I need help with this problem. no coding just math
In January, you buy a new Mustang convertible from a Ford dealer, who of fers you the following maintenance contract: $50 each month except March, June, September and December (this covers a general inspection), $100 every March, June, and September (this covers an oil change, a monor tune-up, a general inspection), and $200 every December (this covers an oil change, a major tune-up, and a general inspection). Calculate an upper bound on the cost of this maintenance contract as a function of n the number of months. Do a worst-case analysis on the contact first. Then do an amortized analysis using the aggregate method. Confirm the amortized cost using the accounting method. And finally, using this potential function: to confirm the amortized cost again.Explanation / Answer
Worst-Case Complexity Analysis:
We can bind the contract cost for the first n months by taking the product of n and the maximum cost incurred in any month (i.e., $200). This would be analogous to the traditional way to estimate the complexity-take the product of the number of operations and the worst-case complexity of an operation. Using this approach, we get $200 X n as an upper bound on the contract cost. The upper bound is correct because the actual cost for n months does not exceed $200 X n.
Amortized Analysis:
Aggregate Method
To use the aggregate method for amortized complexity, we first determine an upper bound on the sum of the costs for the first n months. As tight a bound as is possible is desired. The sum of the actual monthly costs of the contract for the first n months is
200*floor(n/12) + 100*(floor(n/3) - floor(n/12)) + 50*(n - floor(n/3))
= 100*floor(n/12) + 50*floor(n/3) + 50*n
<= 100*n/12 + 50*n/3 + 50*n
= 50n(1/6 + 1/3 + 1)
= 50n(3/2)
= 75n
The amortized cost for each month is set to $75. The table below shows the actual costs, the amortized costs, and the potential function value (assuming P(0) = 0) for the first 16 months of the contract.
month | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
actual cost | 50 50 100 50 50 100 50 50 100 50 50 200 50 50 100 50
amortized cost | 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75
P() | 25 50 25 50 75 50 75 100 75 100 125 0 25 50 25 50
The cumulative difference between what the operations are charged and their actual costs is given by the potential function. When we use the amortized cost of $75 per month, we get $75n as an upper bound on the contract cost for n months. This bound is tighter than the bound of $200n obtained using the worst-case monthly cost.
Accounting Method:
When we use the accounting method, we must first assign an amortized cost for each month. We have the option to assign a different amortized cost to each month. In our maintenance contract example, we know the actual cost by month and could use this actual cost as the amortized cost. It is, however, easier to work with an equal cost assignment for each month.
To get the best upper bound on the sum of the actual costs, we must set the amortized monthly cost to be the smallest number. From the above table, we see that using any cost less than $75 will result in P(n) - P(0) < 0 for some values of n. Therefore, the smallest assignable amortized cost consistent with Equation (3) is $75. Generally, when the accounting method is used, we have not computed the aggregate cost. Therefore, we would not know that $75 is the least assignable amortized cost.
We can obtain an upper bound on the cost of any operation sequence by computing,
sum1 <= i <= k f(i) * amortized(i)
where k is the number of different operation types and f(i) is the frequency of operation type i (i.e., the number of times operations of this type occur in the operation sequence). For our maintenance contract example, we might try an amortized cost of $70. We might next try $80. By constructing a table such as the one above, those is satisfied for all months in the first 12 month cycle, and then conclude that the equation is satisfied for all n. Now, we can use $80n as an upper bound on the contract cost for n months.
Potential Method:
We first define a potential function for the analysis. The only guideline you have in defining this function is that the potential function represents the cumulative difference between the amortized and actual costs. So, if you have an amortized cost in mind, you may be able to use this knowledge to develop a potential function, and then use the potential function and the actual operation costs (or an upper bound on these actual costs) to verify the amortized costs.
amortized(i) = actual(i) + P(i) - P(i-1)
Therefore, amortized(1) = actual(1) + P(1) - P(0) = 50 + 25 - 0 = 75, amortized(2) = actual(2) + P(2) - P(1) = 50 + 50 - 25 = 75, amortized(3) = actual(3) + P(3) - P(2) = 100 + 25 - 50 = 75, and so on. Therefore, the amortized cost for each month is $75. So, the actual cost for n months is at most $75n.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.