independent of whether the sequence is implemented as an array or linked list code fragment quick-sort for an input sequence implemented with linked list or an array running time of quick-sort we can analyze the running time of quick-sort with the same technique used for merge-sort in section namelywe can identify the time spent at each node of the quick-sort tree and sum up the running times for all the nodes examining code fragment we see that the divide step and the conquer step of quick-sort can be implemented in linear time thusthe time spent at node of is proportional to the input size (vof vdefined as the size of the sequence handled by the invocation of quick-sort associated with node since subsequence