Question

Problem 3: does there exist an algorithm that makes at most four comparisons to sort any array of size 4? Why or why not?

Answer 1

Explanation:

Since we are already having the proof that no comparison based algorithm can take less than O(nlogn) time. This implies that if certain algorithm exists, ...