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.