Question

Consider dynamic arrays with geometric expansion and no shrinking. Match operations to their complexity.

Always choose the most informative answer. For instance, if an operation is O(1) and O(n) choose O(1); if an operation is O(1) and O(1) amortized, choose O(1).

Options to choose from are: O(1), O(1) amortized or O(n)

addFirst :

len (length/size) :

deleteLast :

deleteFirst :

addLast (append) :

Answer 1

Since the dynamic array automatically grows when we try to make an insertion and there is no more space left for the new item then we usually, doubles the size of the array and the dynamic array moves itself so that the entire array is contiguous (and so lookup is constant time)

a) addFirst:

TC(Time complexity) for this operation : O(N)

wher, N = size of the dyanmic array

dynamic array moves itself and it is contiguous , therefore In the worst case inserting a new element at First of the dyanmic array we have to move first N element of the array right then we have to insert which will cost O(N).

b) len(length/size)

TC(Time complexity) for this operation : O(1)

finding the length of the dyanmic array with the given index using function property size(array) will give length in O(1) time complexity.

c) deleteLast :

  TC(Time complexity) for this operation : O(1)

Since dyanmic array is contigous so we can go at the last index of the array easily free/ remove the last index element from the array which will cost O(1)

  

d) deleteFirst:

TC(Time complexity) for this operation : O(N)

Since dyanmic array is contigous so we have to shift the n-1 element excluding first element to the left after deleting the first index element of the array which will cost at worst case O(N).

e) addLast(append):

  TC(Time complexity) for this operation : O(1)

   Adding / appending  element at the end of the dyanmic array if dyanmic array length is not enough then it will extend to the length of the dyanmic array and adding / appending element at the end of the original dyanmic array as well as given index which will be doing all that copying takes O(N) time operartions, where N is the number of elements in gien dyanmic  array which will be expensive cost for an append. but in fixed length dyanmic array, adding last / appending  at last only will take O(1) time.