which runs in (ntimebecause we have to shift backward elements in the worst case ( in factassuming that each possible index is equally likely to be passed as an argument to these operationstheir average running time is ( )for we will have to shift / elements on average table performance of an array list with elements realized by an array the space usage is ( )where is the size of the array method time size( ( isempty( ( get(io( set(ieo( add(ieo(nremove(io(nlooking more closely at add(ieand remove( )we note that they each run in time ( )for only those elements at index and higher have to be shifted up or down thusinserting or removing an item at the end of an array listusing the methods add(neand remove( )respectively take ( time each moreoverthis observation has an interesting consequence for the adaptation of the array list adt to the deque adt given in section if the array list adt in this case is implemented by means of an array as described abovethen methods addlast and removelast of the deque each run in (