For each of the following code snippets, match it to the appropriate $($worst$-$case$)$ time or space complexity, as specified at the top of the snippet.

You should assume that the size of the input array a is $.$

If you're unfamiliar with $,$ you should consider looking at the Algorithms Analysis Primer in the Week $0$ sub$-$module.

Note that declaring an array of length n is frequently a operation, as many languages $($including many versions of Java$)$ will initialize each entry of the new array to its default value. You may assume that it is for this problem.

Question $6$ options:

Time complexity of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$(0,$ a$[$i$])$

$($Extra$)$ space complexity $($i$.$e$.$ not including space of array a$)$ of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$(0,$ a$[$i$])$

Time complexity of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$($i$,$ a$[$i$])$

Time complexity of

function$($int$[]$ a$)$

int$[]$ b $=$ new int$[$a$.$length$]$

return a$[0]$

$($Extra$)$ space complexity $($i$.$e$.$ not including space of array a$)$ of

function$($int$[]$ a$)$

return a$[0]$

$($Extra$)$ space complexity $($i$.$e$.$ not including space of array a$)$ of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$($d$.$size$()/2,$ a$[$i$])$

Time complexity of

function$($int$[]$ a$)$

return a$[0]$

$($Extra$)$ space complexity $($i$.$e$.$ not including space of array a$)$ of

function$($int$[]$ a$)$

int$[]$ b $=$ new int$[$a$.$length$]$

return a$[0]$

$($Extra$)$ space complexity $($i$.$e$.$ not including space of array a$)$ of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$($i$,$ a$[$i$])$

Time complexity of

function$($int$[]$ a$)$

d $=$ new ArrayDeque

for$($ i$=0$; i $<$ a$.$length; i$++)$

d$.$add$($d$.$size$()/2,$ a$[$i$])$

$1.$

time

$2.$

space

$3.$

time

$4.$

space

$5.$

time

$6.$

space