Q1. (a) Explain the Quicksort Algorithm for ordering a list L of n objects. Calculate how many comparisons are needed in a quicksort of the list [23, -4, 2, 31, 21] (in your calculations - at any time in the sort where you must choose a pivot, that pivot should be the left-most element of the current (sub)list).

(b) Prove that under best case behaviour, the complexity of quicksort is O (n log n) .

(c) If a quicksort of 10^5 items took 7 seconds under best case behaviour and 20 seconds under worst case behaviour, how long would you expect it to take for a quicksort of

i. 10^7 items under best case behaviour?

ii. 10^4 items under best case behaviour?

iii. 10^6 items under worst case behaviour

Q2. Calculate the computational complexity (in big O notation) of binary search in the

i. best case

ii. worst case

iii. average case scenarios

Q3.

(a) If f(n) = O g(n) and g(n) = O h(n) , use the definition of big O notation to prove that f(n) + 2g(n) + h(n) = O h(n)

c) Suppose that algorithms A1 and A2 have computational complexities of O( n log(n)) and O (n^3) respectively. Both algorithms take approximately 100 seconds to run on data input of size n = 10, 000.

Determine (to the nearest second) the time it will take each algorithm to run on data input of size

i. n = 1, 000

ii. n = 100