A divide-and-conquer algorithm has a 'split' step (dividing the input into subproblems) and a 'combine' step (assembling the result from the solved subproblems). Call a step 'trivial' if it only partitions or concatenates by position, without comparing or rearranging elements, and 'non-trivial' if it does the real work of comparing/rearranging elements. For quicksort, characterise the split and the combine step.

Question

Accepted Answer

non-trivial split, trivial combine

Answer

trivial split, trivial combine

Answer

non-trivial split, non-trivial combine

Answer

trivial split, non-trivial combine

Crowdly

A divide-and-conquer algorithm has a 'split' step (dividing the input into subpr...

Want instant access to all verified answers on learning.monash.edu?