I only need 3-5, thanks ! 2.1 ArrayStacks Recall that an ArrayStack stores n ele

Question

I only need 3-5, thanks !

2.1 ArrayStacks Recall that an ArrayStack stores n elements in a backing array a at locatios0. a[n-1]: public class ArrayStack extends AbstractList Tli a int n; 1. 2. Describe the implementation and running times of the operations get(i) and set(i,x) in an ArrayStack. Recall that the length of the backing array a in an ArrayStack doubles when we try to add an element and n+1> a.length. Explain, in general termswhy we choose to double rather than just add 1 or a constant. 3. Recall that, immediately after an ArrayStack is resized it has a.length 2*n If we are currently about to grow the backing array a, what can you say about the number of add() and remove() operations since the last time the ArrayStack was resized? a. b. Recall that we shrink the back array a when 3*n

Explanation / Answer

As requested only answering the questions requested:-

Answer 3)

a) Now size of arrayStack = 2n

previously when it was resized its size was n/2 (as n/2*2 = n)

So number of add operations - number of remove operations = n/2

b)now it is 3*n

so before it was n/3*3 =n

so number of add - number of remove operations = n-n/3 = 2n/3

4) Number of elements copied = n/3 elements needs to be copied first then empty spaces = 2n/3

5) add(i,x) = O(1)

remove(i)=O(1)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---