Using big-O notation, state the average time and space complexity of quicksort
How do insertions and deletions in a 2-3-4 tree retain the structure’s perfect balance?
March 20, 2023What is the time complexity of binary search on a list of N items?
March 20, 2023Using big-O notation, state the average time and space complexity of quicksort
Algorithms
(a) Using big-O notation, state the average time and space complexity of quicksort.
[2 marks]
(b) What is the worst-case time and space complexity of quicksort? Briefly explain
how this worst-case behaviour can occur. [3 marks]
(c) A programmer implements a two-phase sorting algorithm comprising a partial
quicksort, which does not recurse on list partitions of 10 items or fewer,
followed by an ordinary insertion sort. What is the worst-case time complexity
of the second phase? Explain your answer with the aid of a diagram.
[5 marks]
