Select all the options below that are true about ArrayDeques $($as we learned about them in class; not java's ArrayDeque$).($Ignore amortization.$)$

Note:

just means $"$

but not smaller than

$".$ E$.$g$.$

is an upper bound so technically something that is constant time is still O$($n$).$ That's not usually how I $($or computer scientists in general$)$ use it$,$ but I'll try to be precise.

If you're uncomfortable with

you can probably just think of it as

and you'll probably be using it the way I intend it :-) If you have questions or concerns about big$-$Theta vs$.$ big$-$Oh$,$ you might consider looking at the Week $0$ algorithms analysis primer slides or video.

Question $3$ options:

a$)$

ArrayDeques have

$($i$.$e$.$ bad$)$ insertions at the front.

b$)$

ArrayDeques have

$($i$.$e$.$ bad$)$ removes from the front.

c$)$

ArrayDeques have

$($i$.$e$.$ bad$)$ setting the front element to a different value.

d$)$

ArrayDeques have O$(1)($i$.$e$.$ good$)$ at insertions in the middle.

e$)$

ArrayDeques have O$(1)($i$.$e$.$ good$)$ removes from the middle.

f$)$

ArrayDeques have O$(1)($i$.$e$.$ good$)$ setting an element in the middle to a different value.

g$)$

ArrayDeques have

$($i$.$e$.$ bad$)$ insertions at the back.

h$)$

ArrayDeques have O$($n$)($i$.$e$.$ bad$)$ removals from the back.

i$)$

ArrayDeques have O$($n$)($i$.$e$.$ bad$)$ setting an element at the back to a different value.

j$)$

ArrayDeques' backing storage is a single array of fixed size, so repeated insertions will sooner or later require a resize of that array.

k$)$

If you have a block of b contiguous elements to insert into an ArrayDeque, b individual insertions will require b separate shifts. This will be O$($min$\{$i$,$ n$-$i$\}$b$)($i$.$e$.$ slow$)$ since shifting is O$($min$\{$i$,$ n$-$i$\})($i$.$e$.$ relatively slow.$)$