algorithm analysis create listtemp list(valuelist the first example creates an empty listwhich can be accomplished in constant time the second creates list containing elementswith each element initialized to the actual allocation of the elements can be done in constant timebut the initialization of the individual elements requires list traversal since there are elements and traversal requires linear timethe allocation of vector with elements requires (ntime appending to list the append(operation adds new item to the end of the sequence if the underlying array used to implement the list has available capacity to add the new itemthe operation has best case time of ( since it only requires single element access in the worst casethere are no available slots and the array has to be expanded using the steps described in section creating the new larger array and destroying the old array can each be done in ( time to copy the contents of the old array to the new larger arraythe items have to be copied element by elementwhich requires (ntime combining the times from the three steps yields time of ( and worst case time of (nextending list the extend(operation adds the entire contents of source list to the end of the destination list this operation involves two listseach of which have their own collection of items that may be of different lengths to simplify the analysishoweverwe can assume both lists contain items when the destination list has sufficient capacity to store the new itemsthe entire contents of the source list can be copied in (ntime but if there is not sufficient capacitythe underlying array of the destination list has to be expanded to make room for the new items this expansion requires (ntime since there are currently items in the destination list after the expansionthe items in the source list are copied to the expanded arraywhich also requires (ntime thusin the worst case the extend operation requires (nn or (ntime inserting and removing items inserting new item into list is very similar to appending an item except the new item can be placed anywhere within the listpossibly requiring shift in elements an item can be removed from any element within listwhich may also involve shifting elements both of these operations require linear time in the worst casethe proof of which is left as an exercise