chap limits to computation find one method to convert the inputs to pairing into inputs to sorting "fast enough,and second method to convert the result of sorting back to the correct result for pairing "fast enough,then the asymptotic cost of pairing cannot be more than the cost of sorting in this casethere is little work to be done to convert from pairing to sortingor to convert the answer from sorting back to the answer for pairingso the dominant cost of this solution is performing the sort operation thusan upper bound for pairing is in ( log nit is important to note that the pairing problem does not require that elements of the two sequences be sorted this is merely one possible way to solve the problem pairing only requires that the elements of the sequences be paired correctly perhaps there is another way to do itcertainly if we use sorting to solve pairingthe algorithms will require ohm( log ntime butanother approach might conceivably be faster there is another use of reductions aside from applying an old algorithm to solve new problem (and thereby establishing an upper bound for the new problemthat is to prove lower bound on the cost of new problem by showing that it could be used as solution for an old problem with known lower bound assume we can go the other way and convert sorting to pairing "fast enough what does this say about the minimum cost of pairingwe know from section that the cost of sorting in the worst and average cases is in ohm( log nin other wordsthe best possible algorithm for sorting requires at least log time assume that pairing could be done in (ntime thenone way to create sorting algorithm would be to convert sorting into pairingrun the algorithm for pairingand finally convert the answer back to the answer for sorting provided that we can convert sorting to/from pairing "fast enough,this process would yield an (nalgorithm for sortingbecause this contradicts what we know about the lower bound for sortingand the only flaw in the reasoning is the initial assumption that pairing can be done in (ntimewe can conclude that there is no (ntime algorithm for pairing this reduction process tells us that pairing must be at least as expensive as sorting and so must itself have lower bound in ohm( log nto complete this proof regarding the lower bound for pairingwe need now to find way to reduce sorting to pairing this is easily done take an instance of sorting ( an array of elementsa second array is generated that simply stores in position for < pass the two arrays to pairing take the resulting set of pairsand use the value from the half of the pair to tell which position in the sorted array the half should takethat iswe can now reorder