Explain how the worst-case behaviour of Quicksort can be avoided to yield an improved time complexity
Derive the Correct asymptotic complexity
March 20, 2023How do insertions and deletions in a 2-3-4 tree retain the structure’s perfect balance?
March 20, 2023Explain how the worst-case behaviour of Quicksort can be avoided to yield an improved time complexity
2007 Paper 1 Question 11
Algorithms
(a) Describe how Quicksort works, using the following array of numbers as an
example: 16, 42, 22, 7, 15, 3. [8 marks]
(b) What are the worst-case time and space complexities of Quicksort, and how
can this worst-case behaviour occur? [3 marks]
(c) Explain how the worst-case behaviour of Quicksort can be avoided to yield
an improved time complexity. Would the changes you describe be useful in
practice? [9 marks]
