Algorithms
(a) What is the time complexity of binary search on a list of N items? [1 mark]
(b) Binary search requires list items to be in sorted order. What is the best
possible worst-case time complexity achievable by a comparison-based sorting
algorithm? Credit will be given for a clear explanation of your answer, but
there is no need to provide a formal mathematical analysis or proof. [7 marks]
(c) A researcher proposes a ternary search algorithm which repeatedly compares
the search key with the two list items that most accurately trisect the
remaining sorted search space.
(i) Derive asymptotic expressions for the number of list items queried by
binary search and by ternary search in the worst case. Explain your
derivations in terms of worst-case executions of the search algorithms.
[6 marks]
(ii) Approximately how many extra list items are queried by a ternary search
compared with an equivalent binary search, in the worst case? Express
your answer as a numeric percentage. If required, you may assume that
the list being searched is very large and that log2
(3) ≈ 1.6. [6 marks]