我们做出如下断言：无论采用何种比较算法，第二小的元素在我们找寻最小元素的过程中一定与最小元素发生过比较。
这是显然的，因为第二小元素在与除最小元素外的其他任何元素进行比较时一定都会胜出（被选中进入下一轮比较），若最小元素不与第二小元素进行比较则无法确定二者之间的大小关系，从而无法得出最小值。
因而，要想使我们找到第二小的元素使用的比较次数尽量少，我们需要使找寻最小元素的过程中与最小元素发生过比较的元素尽量少。
由于每次我们只能取两个数进行比较，从而考虑每一轮比较我们将待比较元素两两分组比较，较小的元素进入下一轮继续比较（若总元素个数为奇数，落单的元素直接进入下一轮比较），这样比较所得的与最小元素比较过的元素是最少的（每一轮只有一个）。
我们将比较过程组织成一棵二叉树（以数组1 3 2 5 6 7 4为例）：
其中，每一个结点都是其两个子结点比较所得结果。在树的每一层只有一个元素与于最小元素比较（除第一层外）。该比较算法中比较次数等于树中度为2的结点个数，由二叉树的性质可知，该二叉树找寻最小元素对应的比较次数为n-1次（二叉树中：度为2的结点个数=度为零的结点个数-1）达到了下界，从而是最优的。可以看出，与最小元素比较的元素个数=树高h-1。又叶节点个数为n从而有2^(h-1）>=n，故有h-1=ceil(lgn)即与最小元素比较的元素个数至少为ceil(lgn)。
从这ceil(lgn)个元素中找到最小元素即为第二小元素。最坏情况下，在第一轮比较中，第二小元素与第一小元素比较而被淘汰，从而在得到最小元素的过程中，我们无法得到其余任何元素与第二小元素的大小关系。在这种情况下，要找出这ceil(lgn)个元素中的最小元素需要ceil(lgn)-1次比较。
综上，最坏情况下，找出第二小元素所需的比较次数为n-1+ceil(lgn)-1=n+ceil(lgn)-2。