Derive the Correct asymptotic complexity
Carefully describe the purpose and structure of a skip list
March 20, 2023Explain how the worst-case behaviour of Quicksort can be avoided to yield an improved time complexity
March 20, 2023Derive the Correct asymptotic complexity
Algorithms
For each of the following, indicate whether the statement is true or false, and explain
why this is the case (you do not need to derive the correct asymptotic complexity
yourself, but no marks will be awarded for an answer with no explanation).
(a) Heapsort executes in worst-case O(n
2
) time. [2 marks]
(b) Insertion sort executes in worst-case Θ(n
2
) time. [2 marks]
(c) Shellsort executes in worst-case Ω(n
1.5
) time. [2 marks]
(d) All sorting algorithms are Ω(n log n). [2 marks]
(e) A linked list is faster to access than a splay tree. [2 marks]
