I am having trouble with the following homework assignment:
Give an algorithm that finds the second smallest of n elements in at most $n + \lceil\log(n)\rceil - 2$ comparisons.
I have been trying to find an algorithm myself, and believe I have to check the elements in pairs and then recurse on the smallest elements. However, when I tried an algorithm like this the amount of comparisons it took where $n + \lceil\log(n)\rceil$ (according to me).
This is the algorithm in question:
1. secondSmallest(A[n]) 2. if A.length >= 2 then 3. for i = 1 to i = A.length do 4. if A[i] < A[i + 1] then 5. B[(i+1)/2] = A[i] 6. i + + 7. else 8. B[(i+1)/2] = A[i + 1] 9. i + + 10. endif 11. return secondSmallest(B[n]) 12. else 13. if A[1] < A[2] then 14. return A[2] 16. else return A[1] 17. endif 18. endif
Note: this is pseudocode, and by no means accurate. And the logarithm is a BASE 2 logarithm.