This was already answered, but I don\'t understand the submitted solution. Any e
ID: 3750780 • Letter: T
Question
This was already answered, but I don't understand the submitted solution. Any explanation to the values you obtain for B would be appreciated.
Consider the operation of filling an empty ArrayList with values. The initial capacitycapacity, we increase the capacity by calling increaseCapacity capacity 10 II change array size and copy over Let D (n) be the total number of element copy operations which have taken place when the array size has just exceeded n elements. a. Prove that D (n) - 2 (n2) Proceed as follows: Consider only n10, 20, 30, 40, 50, satisfies this recurrence relation: and observe that D(n) D(1010 D (n) D(n - 10) + n, n e 20 Compute several values of D (n) and n2. Find a (small) constant c > 0 and prove by induction that D(n) - c * n2, n 20 b. Based on the answer in part (a), determine the average cost for a single add operation. Express your answer in the "order terminology" and explain your reasoning.Explanation / Answer
a.
To Prove: D(n) = (n2)
Reccursion: D(10) = 10
D(n) = D(n-10) + n, for n >= 20
Guessing the solution to be D(n) = (n2)
therefore need to Prove D(n) >= c * n2 for some constant c
As our inductive hypothesis, we assume D(n) >= c * n2
D(n) = D(n-10) + n
= D(n-20) + n-10 + n = D(n-20) + 2n -10
= D(n-30) + n-20 +n-10 + n = D(n-30) + 3n -10 - 20
= D(n-40) + n-30 + n-20 +n-10 +n = D(n-40) + 4n -10 -20 - 30
= D(n-50) + n-40+n-30 + n-20+ n-10 + n = D(n-50) + 5n -10-20-30-40
|
|
=D(n-10*k) + kn - 10(1+2+3+4 ..........+ k-1)
=D(n-10*k) + kn - 10(k-1)(k-2)/2
=D(n-10*k) +kn - 10(k2 - 3k + 2)/2
concidering n-10*k = 10 as D(10)=10 so 10k = n-10 or k = n-10
therefore
>= D(10) + n-10*n -10(n2) . -------- changed due to obselating some constant values
>= 10 +n2 +c*n2
>= c*n2
As D(n) >= c*n2
Therefore D(n) = (n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.