creativity - linda claims to have an algorithm that takes an input sequence and produces an output sequence that is sorting of the elements in give an algorithmis sortedthat tests in (ntime if is sorted explain why the algorithm is sorted is not sufficient to prove particular output to linda' algorithm is sorting of describe what additional information linda' algorithm could output so that her algorithm' correctness could be established on any given and in (ntime - describe and analyze an efficient method for removing all duplicates from collection of elements - augment the positionallist class (see section to support method named merge with the following behavior if and are positionallist instances whose elements are sortedthe syntax merge(bshould merge all elements of into so that remains sorted and becomes empty your implementation must accomplish the merge by relinking existing nodesyou are not to create any new nodes - augment the positionallist class (see section to support method named sort that sorts the elements of list by relinking existing nodesyou are not to create any new nodes you may use your choice of sorting algorithm - implement bottom-up merge-sort for collection of items by placing each item in its own queueand then repeatedly merging pairs of queues until all items are sorted within single queue - modify our in-place quick-sort implementation of code fragment to be randomized version of the algorithmas discussed in section - consider version of deterministic quick-sort where we pick as our pivot the median of the last elements in the input sequence of elementsfor fixedconstant odd number > what is the asymptotic worst-case running time of quick-sort in this casec- another way to analyze randomized quick-sort is to use recurrence equation in this casewe let (ndenote the expected running time of randomized quick-sortand we observe thatbecause of the worst-case partitions for good and bad splitswe can write ( < ( ( / ( / )( ( )bn where bn is the time needed to partition list for given pivot and concatenate the result sublists after the recursive calls return showby inductionthat (nis ( log