RootishArrayStack

Question 1

What is the runtime of get(i) for a RootishArrayStack?

Answer 1

O(1)

Question 2

What is the runtime of set(i,x) for a RootishArrayStack?

Answer 2

O(1)

Question 3

What is the runtime of add(i,x) for a RootishArrayStack?

Answer 3

O(n-i) amortized

Question 4

What is the runtime of remove(i) for a RootishArrayStack?

Answer 4

O(n-i) amortized

Question 5

What is the extra space required for a RootishArrayStack to store n elements?

Answer 5

O(sqrt(n))

Question 6

What is the backing storage in a RootishArrayStack?

Answer 6

O(sqrt(n)) arrays of sizes 1, 2, 3, 4, ….

Question 7

The first r blocks of a RootishArrayStack can store up to how many elements?

Answer 7

r(r+1)/2.

The first r blocks have capacity 1, 2, 3, 4, …, r and 1+2+3+…+r = r(r+1)/2

Question 8

What index i yields the worst-case running time for the add(i,x) operation in a RootishArrayStack?

Answer 8

index i=0.

Adding to the first position requires all remaining n elements to be shifted to the right, which is O(n) work.

Question 9

What index i yields the best-case running time for the add(i,x) operation in a RootishArrayStack?

Answer 9

index i=n-1.

I.e. adding to the end is fast since it doesn’t require much shifting. You may need to add a new block, but allocating a new block does not take much time in most systems.

Question 10

Pros of RootishArrayStacks.

Answer 10

Use only O(sqrt(n)) extra space to store n elements.
Fast get(i) and set(i,x) (i.e. good random access)
Its runtimes are not even amortized, unless array allocation is not constant time (and if it isn't constant, it's still good amortized time.)

Question 11

Cons of RootishArrayStacks

Answer 11

Slightly more complex implementation than some other array-based implementations of the list interface.
Adding and removing from the front is O(n), so this is not a good choice to implement the Deque interface.