the records in the array using the corresponding value in the array as the sort key and running simple th(nbinsort the conversion of sorting to pairing can be done in (ntimeand likewise the conversion of the output of pairing can be converted to the correct output for sorting in (ntime thusthe cost of this "sorting algorithmis dominated by the cost for pairing consider any two problems for which suitable reduction from one to the other can be found the first problem takes an arbitrary instance of its inputwhich we will call iand transforms to solutionwhich we will call sln the second problem takes an arbitrary instance of its inputwhich we will call and transforms to solutionwhich we will call sln we can define reduction more formally as three-step process transform an arbitrary instance of the first problem to an instance of the second problem in other wordsthere must be transformation from any instance of the first problem to an instance of the second problem apply an algorithm for the second problem to the instance yielding solution sln transform sln to the solution of iknown as sln note that sln must in fact be the correct solution for for the reduction to be acceptable figure shows graphical representation of the general reduction processshowing the role of the two problemsand the two transformations figure shows similar diagram for the reduction of sorting to pairing it is important to note that the reduction process does not give us an algorithm for solving either problem by itself it merely gives us method for solving the first problem given that we already have solution to the second more importantly for the topics to be discussed in the remainder of this reduction gives us way to understand the bounds of one problem in terms of another specificallygiven efficient transformationsthe upper bound of the first problem is at most the upper bound of the second converselythe lower bound of the second problem is at least the lower bound of the first as second example of reductionconsider the simple problem of multiplying two -digit numbers the standard long-hand method for multiplication is to multiply the last digit of the first number by the second number (taking th(ntime)multiply the second digit of the first number by the second number (again taking th(ntime)and so on for each of the digits of the first number finallythe intermediate results are added together note that adding two numbers of length and can easily be done in th( + time because each digit of the first number is multiplied against each digit of the secondthis algorithm requires th( time