It seems that keeping track of all elements which lost to the best requires O(n) space or extra O(n) comparisons.
It is interesting that the same time complexity can be achieved by iterating the array and comparing each element to the second smallest (initialize it with first element). If compared element is smaller, compare it with the first smallest and decide if only second smallest needs to be updated or first smallest has to be copied to second smallest and then updated with compared element. It turns out that number of times compared element is smaller than the second smallest element is O(lgn), thus number of comparisons needed fits the question.
I couldn't prove this asymptotic theoretically yet, although it reproduced in practice. Maybe someone could help with the proof.
It seems that keeping track of all elements which lost to the best requires O(n) space or extra O(n) comparisons.
It is interesting that the same time complexity can be achieved by iterating the array and comparing each element to the second smallest (initialize it with first element). If compared element is smaller, compare it with the first smallest and decide if only second smallest needs to be updated or first smallest has to be copied to second smallest and then updated with compared element. It turns out that number of times compared element is smaller than the second smallest element is O(lgn), thus number of comparisons needed fits the question.
I couldn't prove this asymptotic theoretically yet, although it reproduced in practice. Maybe someone could help with the proof.