proportional to even in the best casesince they each require searching the entire list to find minimum-key entry that isusing the notation of section we can say that these methods run in th(ntime finallywe implement methods size and isempty by simply returning the output of the corresponding methods executed on list thusby using an unsorted list to implement priority queuewe achieve constant-time insertionbut linear-time search and removal implementation with sorted list an alternative implementation of priority queue also uses list sexcept that this time let us store the entries sorted by key specificallywe represent the priority queue by using list of entries sorted by nondecreasing keyswhich means that the first element of is an entry with the smallest key fast removals and slow insertions we can implement method min in this case simply by accessing the first element of the list with the first method of likewisewe can implement the removemin method of as remove( first()assuming that is implemented with doubly linked listoperations min and removemin in take ( time thususing sorted list allows for simple and fast implementations of priority queue access and removal methods this benefit comes at costhoweverfor now method insert of requires that we scan through the list to find the appropriate position to insert the new entry thusimplementing the insert method of now takes (ntimewhere is the number of entries in at the time the method is executed in summarywhen using sorted list to implement priority queueinsertion runs in linear time whereas finding and removing the minimum can be done in constant time comparing the two list-based implementations table compares the running times of the methods of priority queue realized by means of sorted and unsorted listrespectively we see an interesting tradeoff when we use list to implement the priority queue adt an unsorted list allows for fast insertions but slow queries and deletionswhile sorted list allows for fast queries and deletionsbut slow insertions table worst-case running times of the methods of priority queue of size nrealized by