An algorithm is defined as an unambiguous procedure that contains a finite set of well-defined operations or steps that requires a finite amount of storage and takes a finite amount of time to complete and it can be executed by a mathematical machine [ 1]. The word ‘Algorithmic’ is defined as a branch of computer science that consists of both designing and analyzing algorithms. The word “design” pertains to the description of the algorithm at the abstract level through a pseudo-language. The algorithm’s correctness is that it should solve the given problem in all cases. Next, the “analysis” part deals with the performance evaluation of the algorithm, also defined as the complexity analysis. This paper designs an optimal algorithm to find the second smallest among the given n numbers [ 2,3,4]. The complexity analysis and the advantages of the proposed algorithm are also explored in the next sections. Optimal algorithms should be designed to solve real-world problems either using hard computing or soft computing techniques [ 5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29].

The following are the important characteristics of every algorithm [ 3].

An algorithm must be precise.

An algorithm must be effective.

An algorithm must have a fixed finite number of instructions.

The execution of an algorithm must always terminate

The optimal algorithm to find the second smallest among n numbers is designed to the properties mentioned in section 2 and the resultant optimal algorithm is presented in this section.

Algorithm Find-SecondMin (A[ ], n)

// A[1: n] is an one-dimensional array, that contains n elements

// Finding the second smallest among n elements with minimum comparisons, O(n)

1: fmin =A[ 1]; smin = A[ 2];

2: if (smin < fmin) then fmin = A[ 2]; smin = A[ 1];

3: for i = 3 to n do:

4: if (fmin = smin) then smin=A[i];

5: if (A[i] < fmin) then smin = fmin; fmin = A[i];

6: else if ((fmin < A[i]) &#x00026;&#x00026; (A[i] < smin)) then smin = A[i];

7: // End of Algorithm

The best, worst, and average-case analysis of the devised algorithm is explained in this section [ 4,5].

Worst case: The total count of basic operations, that is, the count of comparisons performed in the worst case is given by

w(n) = 1 + (n &#x02013; 2 + 1)[ ] = 1 + 4(n &#x02013; 1) = 1 + 4n &#x02013; 4 = 4n &#x02013; 3 = O(n).

For example, n =5, and the inputs (80, 30, 35, 34, 32) result in worst-case performance.

Average case: The total count of basic operations, that is, the count of comparisons performed in the average case is given by

A(n) = 1 + (n &#x02013; 2 + 1) [ ] = 1 + 3(n &#x02013; 1) = 1 + 3n &#x02013; 3 = 3 n &#x02013; 2 = O(n).

For example, n =5 and the inputs (10, 20, 30, 40, and 50) result in average-case performance.

Best case: The total number of basic operations, that is, the number of comparisons performed in the best case is given by

f(n) = 1 + (n &#x02013; 2 + 1) [ ] = 1 + 2(n &#x02013; 1 ) = 1 + 2 n &#x02013; 2 = 2 n &#x02013; 1 = O(n).

For example, n = 5, and the inputs (10, 8, 5, 3, and 2) result in best-case performance.

The advantages of the proposed algorithm are presented below.

It takes linear time complexity, O(n). Sorting and finding the 2^nd smallest requires O(n²) time complexity, hence it is an optimal algorithm for n (>=4) values.

The first smallest element is also computed and stored in the variable fmin. Hence applicable in determining the initial solution using the approximation method of Vogel.

If the first smallest, say x, appears in more than one location, and if the next smallest, say y, is available in the input set, then fmin = x and smin = y. If all inputs are the same, then fmin = smin.

In general, in the worst case, an algorithm x is said to be optimal if no algorithm computes less number of basic operations. Here we meant all possible available algorithms, including those not yet designed. Hence, the word &#x0201c;optimal&#x0201d; doesn&#x02019;t mean &#x0201c;the best known&#x0201d;, it means &#x0201c;the best possible&#x0201d;. This paper explained the design of an optimal algorithm for finding the second smallest among n numbers. The computational complexity of the devised algorithm is analyzed for all three cases and its advantages are also discussed.